fbpx

C++: Knapsack Problem

Bjarne-stroustrup
 


A tourist wants to make a good trip at the weekend with his friends. They will go to the mountains to see the wonders of nature, so he needs to pack well for the trip. He has a good knapsack for carrying things, but knows that he can carry a maximum of only 4kg in it and it will have to last the whole day. He creates a list of what he wants to bring for the trip but the total weight of all items is too much. He then decides to add columns to his initial list detailing their weights and a numerical value representing how important the item is for the trip.

Here is the list:

Table of potential knapsack items
item weight (dag) value
map 9 150
compass 13 35
water 153 200
sandwich 50 160
glucose 15 60
tin 68 45
banana 27 60
apple 39 40
cheese 23 30
beer 52 10
suntan cream 11 70
camera 32 30
T-shirt 24 15
trousers 48 10
umbrella 73 40
waterproof trousers 42 70
waterproof overclothes 43 75
note-case 22 80
sunglasses 7 20
towel 18 12
socks 4 50
book 30 10
knapsack ≤400 dag  ?

The tourist can choose to take any combination of items from the list, but only one of each item is available. He may not cut or diminish the items, so he can only take whole units of any item.

Which items does the tourist carry in his knapsack so that their total weight does not exceed 400 dag [4 kg], and their total value is maximised?

[dag = decagram = 10 grams]

#include <vector>
#include <string>
#include <iostream>
#include <boost/tuple/tuple.hpp>
#include <set>
 
int findBestPack( const std::vector<boost::tuple<std::string , int , int> > & , 
      std::set<int> & , const int  ) ;
 
int main( ) {
   std::vector<boost::tuple<std::string , int , int> > items ;
   //===========fill the vector with data====================
   items.push_back( boost::make_tuple( "" , 0  ,  0 ) ) ;
   items.push_back( boost::make_tuple( "map" , 9 , 150 ) ) ;
   items.push_back( boost::make_tuple( "compass" , 13 , 35 ) ) ;
   items.push_back( boost::make_tuple( "water" , 153 , 200 ) ) ;
   items.push_back( boost::make_tuple( "sandwich", 50 , 160 ) ) ;
   items.push_back( boost::make_tuple( "glucose" , 15 , 60 ) ) ;
   items.push_back( boost::make_tuple( "tin", 68 , 45 ) ) ;
   items.push_back( boost::make_tuple( "banana", 27 , 60 ) ) ;
   items.push_back( boost::make_tuple( "apple" , 39 , 40 ) ) ;
   items.push_back( boost::make_tuple( "cheese" , 23 , 30 ) ) ;
   items.push_back( boost::make_tuple( "beer" , 52 , 10 ) ) ;
   items.push_back( boost::make_tuple( "suntan creme" , 11 , 70 ) ) ;
   items.push_back( boost::make_tuple( "camera" , 32 , 30 ) ) ;
   items.push_back( boost::make_tuple( "T-shirt" , 24 , 15 ) ) ;
   items.push_back( boost::make_tuple( "trousers" , 48 , 10 ) ) ;
   items.push_back( boost::make_tuple( "umbrella" , 73 , 40 ) ) ;
   items.push_back( boost::make_tuple( "waterproof trousers" , 42 , 70 ) ) ;
   items.push_back( boost::make_tuple( "waterproof overclothes" , 43 , 75 ) ) ;
   items.push_back( boost::make_tuple( "note-case" , 22 , 80 ) ) ;
   items.push_back( boost::make_tuple( "sunglasses" , 7 , 20 ) ) ;
   items.push_back( boost::make_tuple( "towel" , 18 , 12 ) ) ;
   items.push_back( boost::make_tuple( "socks" , 4 , 50 ) ) ;
   items.push_back( boost::make_tuple( "book" , 30 , 10 ) ) ;
   const int maximumWeight = 400 ;
   std::set<int> bestItems ; //these items will make up the optimal value
   int bestValue = findBestPack( items , bestItems , maximumWeight ) ;
   std::cout << "The best value that can be packed in the given knapsack is " <<
      bestValue << " !\n" ;
   int totalweight = 0 ;
   std::cout << "The following items should be packed in the knapsack:\n" ;
   for ( std::set<int>::const_iterator si = bestItems.begin( ) ; 
	 si != bestItems.end( ) ; si++ ) { 
      std::cout << (items.begin( ) + *si)->get<0>( ) << "\n" ;
      totalweight += (items.begin( ) + *si)->get<1>( ) ;
   }
   std::cout << "The total weight of all items is " << totalweight << " !\n" ;
   return 0 ;
}
 
int findBestPack( const std::vector<boost::tuple<std::string , int , int> > & items ,std::set<int> & bestItems , const int weightlimit ) {
   //dynamic programming approach sacrificing storage space for execution
   //time , creating a table of optimal values for every weight and a 
   //second table of sets with the items collected so far in the knapsack
   //the best value is in the bottom right corner of the values table,
   //the set of items in the bottom right corner of the sets' table.
   const int n = items.size( ) ;
   int bestValues [ n ][ weightlimit ] ;
   std::set<int> solutionSets[ n ][ weightlimit ] ;
   std::set<int> emptyset ;
   for ( int i = 0 ; i < n ; i++ ) {
      for ( int j = 0 ; j < weightlimit  ; j++ ) {
	 bestValues[ i ][ j ] = 0 ;
	 solutionSets[ i ][ j ] = emptyset ;
       }
    }
    for ( int i = 0 ; i < n ; i++ ) {
       for ( int weight = 0 ; weight < weightlimit ; weight++ ) {
	  if ( i == 0 )
	     bestValues[ i ][ weight ] = 0 ;
	  else  {
	     int itemweight = (items.begin( ) + i)->get<1>( ) ; 
	     if ( weight < itemweight ) {
		bestValues[ i ][ weight ] = bestValues[ i - 1 ][ weight ] ;
		solutionSets[ i ][ weight ] = solutionSets[ i - 1 ][ weight ] ;
	     } else { // weight >= itemweight
		if ( bestValues[ i - 1 ][ weight - itemweight ] + 
		   (items.begin( ) + i)->get<2>( ) >
		        bestValues[ i - 1 ][ weight ] ) {
		   bestValues[ i ][ weight ] = 
		       bestValues[ i - 1 ][ weight - itemweight ] + 
	        	(items.begin( ) + i)->get<2>( ) ;
		  solutionSets[ i ][ weight ] = 
		      solutionSets[ i - 1 ][ weight - itemweight ] ;
		  solutionSets[ i ][ weight ].insert( i ) ;
	     }
	     else {
		bestValues[ i ][ weight ] = bestValues[ i - 1 ][ weight ] ;
		solutionSets[ i ][ weight ] = solutionSets[ i - 1 ][ weight ] ;
	     }
	  }
       }
      }
    }
    bestItems.swap( solutionSets[ n - 1][ weightlimit - 1 ] ) ;
    return bestValues[ n - 1 ][ weightlimit - 1 ] ;
}
Output:
The best value that can be packed in the given knapsack is 1030 !
The following items should be packed in the knapsack:
map
compass
water
sandwich
glucose
banana
suntan creme
waterproof trousers
waterproof overclothes
note-case
sunglasses
socks
The total weight of all items is 396 !

SOURCE

Content is available under GNU Free Documentation License 1.2