JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Dynamic Programming: From novice to advanced Memoized 0/1 knapsack problem
 Memoized 0/1 knapsack problem | Reply Hi people, I am trying to write the memoized top-down version of the 0/1 knapsack problem for large problem instances i.e items <= 1000 , knapsackCapacity <= 2*10^7, and following is the code that I have developed so far but this still outputs wrong solution, I have tried hard to debug the code but I am not able to find where am I going wrong in the logic, I would be grateful if someone could suggest where am I going wrong.```// I/O Includes   #include #include #include #include #include #include #include #include #include   // Data Structure Includes   #include #include #include #include #include #include #include #include #include #include #include   // Standard Namespace Inclusion   using namespace std;   // Supporting Macros   #define SZ( C ) ( ( int ) ( ( C ).size() ) ) #define ALL( C ) ( C ).begin() , ( C ).end() #define TR( C , it ) for( typeof( ( C ).begin() ) it = ( C ).begin(); it != ( C ).end() ; ++it ) #define LN( STRING ) ( ( int ) ( STRING ).length() ) #define SPRESENT( C , x ) ( ( ( C ).find( x ) ) != ( C ).end() ) #define CPRESENT( C , x ) ( find( ALL( C ) , x ) != ( C ).end() ) #define PB push_back   // Typedefed Versions of Data Types   typedef vector< int > VI; typedef vector< VI > VVI; typedef vector< string > VS; typedef pair< int ,int > PII; typedef long long LL; typedef unsigned long long ULL;   // this vector will store all the items provided to us vector< pair< itemValue , itemWeight > > vector< pair< int , int > > items;   // this map will serve as a search table for our memoized top-down recursive procedure to compute the optimal value // map< pair< nItems , knapsackSize > , optimalValue > map< pair< int , int > , int > searchTable;   // this function will help us evaluate the optimal value for the respective number of items and a given knapsack capacity int computeOptimal(int nItems , int knapsackCapacity);   int main(){ int knapsackSize; cin >> knapsackSize;   int nItems; cin >> nItems;   // this is a dummy item that we have added items.PB( make_pair( 0 , 0 ) );   for(int i = 0 ; i < nItems ; ++i){   int tempVal , tempWeight; cin >> tempVal >> tempWeight;   items.PB( make_pair( tempVal , tempWeight ) ); }   // now we call the computeOptimal function to evaluate the optimal value for the given number of items and the knapsack // size computeOptimal(nItems , knapsackSize);   cout << "The optimal value is : " << ( (searchTable.find( make_pair( nItems , knapsackSize ) ) ) -> second )<< endl;   return 0; }   int computeOptimal(int nItems , int knapsackCapacity){   if( nItems == 0 || knapsackCapacity == 0) return 0;   else{   // if the value for the given number of items and a given knapsack capacity is already present in the map // just return the value if( searchTable.find( make_pair( nItems , knapsackCapacity ) ) != searchTable.end() ){ return ( ( searchTable.find( make_pair( nItems , knapsackCapacity ) ) ) -> second ); }   else{   if( items[ nItems ].second > knapsackCapacity ){ searchTable.insert( make_pair( make_pair( nItems , knapsackCapacity ) , computeOptimal(nItems - 1 , knapsackCapacity) ) ); }   else{ searchTable.insert( make_pair( make_pair( nItems , knapsackCapacity ) , max( items[nItems].first + computeOptimal( nItems - 1 , knapsackCapacity - items[nItems].second ), computeOptimal(nItems - 1 , knapsackCapacity) ) ) ); } } } } ```Thanks in advance :)
 Forums Tutorial Discussions Dynamic Programming: From novice to advanced Memoized 0/1 knapsack problem Previous Thread  |  Next Thread