0/1 KnapSack Algorithm Source code



// @BEGIN_OF_SOURCE_CODE

int main ()
{
    // number of objects that are available to carry 
    int numberOfObjects;
    	
    // maximum limit that you may take 
    int maxVolumeLimit; 			
    
    // the value of each object that you will get if you take a particular object 
    int valueOfEachObject [numberOfObjects]; 		
    
    // the weight of each object that you will loose from you limit if you 
    // take a particular object 
    int weightOfEachObject [numberOfObjects]; 	

    // the memoizition array
    int dp [numberOfObjects]; 	
    
    // reset the dp array, initially set 0 to all elements 
    memset (dp, 0, sizeof (dp));


    // this algorithm is applicable when you may take an object at most once  
    // ******************* Start *******************
    
    // loop through the numberOfObjects and each time you will check that whether  
    // you are going to take this particular object 
    for ( j = 0; j < numberOfObjects; j++ ) {
            
        // initially you have maxVolumeLimit and gradually it will decrease to zero 
        for ( availableLimit = maxVolumeLimit; availableLimit >= 0; availableLimit-- ) {
            
            if ( weightOfEachObject [j] <= availableLimit && 
                dp [availableLimit] < dp [availableLimit - weightOfEachObject [j]] + valueOfEachObject [j] )
                
                dp [availableLimit] = dp [availableLimit - weightOfEachObject [j]] + valueOfEachObject [j];
        }
    }
    // ******************* End *******************

    // this algorithm is applicable when you may take an object multiple times 
    // ******************* Start *******************
    
    // if you want to find the trace of the objects that have been added to final collection    
    int lastAdded [maxVolumeLimit]; 
    memset (lastAdded, -1, sizeof (lastAdded));

    // if we have availableLimit == x then which object we should take
    for ( availableLimit = 0; availableLimit <= maxVolumeLimit; availableLimit++ ) {
            
        for ( j = 0; j < numberOfObjects; j++ ) {
            
            if ( weightOfEachObject [j] <= availableLimit && 
                dp [availableLimit] < dp [availableLimit - weightOfEachObject [j]] + valueOfEachObject [j] ) {
                        
                dp [availableLimit] = dp [availableLimit - weightOfEachObject [j]] + valueOfEachObject [j];
                // we are taking j-th object (starting 0) in this case 
                lastAdded [availableLimit] = j;
            }
        }
    }
    // ******************* End *******************

    print (dp [maxVolumeLimit]);
}

// @END_OF_SOURCE_CODE

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s