JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
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<new>
#include<cstdio>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<strstream>
 
// Data Structure Includes
 
#include<map>
#include<set>
#include<list>
#include<stack>
#include<deque>
#include<queue>
#include<vector>
#include<bitset>
#include<string>
#include<iterator>
#include<algorithm>
 
// 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 :)
RSS