C++: Continuous Knapsack Problem

A robber burgles a butcher’s shop, where he can select from some items. He knows the weights and prices of each items. Because he has a knapsack with 15 kg maximal capacity, he wants to select the items such that he would have his profit maximized. He may cut the items; the item has a reduced price after cutting that is proportional to the original price by the ratio of masses. That means: half of an item has half the price of the original.

This is the item list in the butcher’s:

Table of potential knapsack items
Item	Weight (kg)	Price (Value)
beef	3.8	36
pork	5.4	43
ham	3.6	90
greaves	2.4	45
flitch	4.0	30
brawn	2.5	56
welt	3.7	67
salami	3.0	95
sausage	5.9	98
Knapsack	<=15 kg	?

Which items does the robber carry in his knapsack so that their total weight does not exceed 15 kg, and their total value is maximised?

#include<iostream>
#include<algorithm>
#include<string.h>
 
using namespace std;
double result;
double capacity = 15;
int NumberOfItems;
int number;
 
struct items
{
    char name[32];
    double weight;
    double price;
    double m;
} item[256];
 
bool cmp(items a,items b)
{
    return a.price/a.weight > b.price/b.weight; // the compare function for the sorting algorithm
}
 
int main()
{
NumberOfItems=9;
strcpy(item[1].name,"beef");
item[1].weight=3.8;
item[1].price=36;
 
strcpy(item[2].name,"pork");
item[2].weight=5.4;
item[2].price=43;
 
strcpy(item[3].name,"ham");
item[3].weight=3.6;
item[3].price=90;
 
strcpy(item[4].name,"greaves");
item[4].weight=2.4;
item[4].price=45;
 
strcpy(item[5].name,"flitch");
item[5].weight=4.0;
item[5].price=30;
 
strcpy(item[6].name,"brawn");
item[6].weight=2.5;
item[6].price=56;
 
strcpy(item[7].name,"welt");
item[7].weight=3.7;
item[7].price=67;
 
strcpy(item[8].name,"salami");
item[8].weight=3.0;
item[8].price=95;
 
strcpy(item[9].name,"sausage");
item[9].weight=5.9;
item[9].price=98;
 
 
sort(item+1,item+NumberOfItems+1,cmp); // We'll sort using Introsort from STL
 
 number = 1;
 while(capacity>0&&number<=NumberOfItems)
 {
  if(item[number].weight<=capacity)
    {
        result+=item[number].price;
        capacity-=item[number].weight;
        item[number].m=1;
    }
  else
  {
      result+=(item[number].price)*(capacity/item[number].weight);
      item[number].m=(capacity/item[number].weight);
      capacity=0;
 
  }
  ++number;
 }
 
cout<<"Total Value = "<<result<<'\n';
cout<<"Total Weight = "<<(double)15-capacity<<'\n';
cout<<"Items Used:\n";
for(int i=1;i<=NumberOfItems;++i)
    if(item[i].m)
    {
       cout<<"We took "<<item[i].m*item[i].weight<<"kg of \""<<item[i].name<<"\" and the value it brought is "<<item[i].price*item[i].m<<"\n";
    }
 
return 0;
}

Alternate Version

// C++11 version
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
 
using namespace std;
 
struct item_type
{
    double  weight, value;
    string  name;
};
 
vector< item_type > items =
{
    { 3.8, 36, "beef"    },
    { 5.4, 43, "pork"    },
    { 3.6, 90, "ham"     },
    { 2.4, 45, "greaves" },
    { 4.0, 30, "flitch"  },
    { 2.5, 56, "brawn"   },
    { 3.7, 67, "welt"    },
    { 3.0, 95, "salami"  },
    { 5.9, 98, "sausage" }
};
 
int main()
{
    sort
    ( 
        begin( items ), end( items ),
        [] (const item_type& a, const item_type& b)
        {
            return a.value / a.weight > b.value / b.weight;
        }
    );
 
    double space = 15;
 
    for ( const auto& item : items )
    {
        if ( space >= item.weight )
            cout << "Take all " << item.name << endl;
        else 
        {
            cout << "Take " << space << "kg of " << item.name << endl;
            break;
        }
 
        space -= item.weight;
    }
}