Computer Science‎ > ‎

Algorithms: Dynamic Programming - The Integer Knapsack Problem with C Program Source Code





Given n items of weight wi and value vi, find the items that should be taken such that the weight is less than the maximum weight W and the corresponding total value is maximum. This problem exhibits both overlapping subproblems and optimal substructure and is therefore a good candidate for dynamic programming.

Complexity:

Time complexity is O(n*W), where n is the total number of items and W is the maximum weight.

Complete Tutorial with Examples :



Integer Knapsack Problem - C Program Source Code

#include<stdio.h>
int max(int a,int b)
{
       
return a>b?a:b;
}
int Knapsack(int items,int weight[],int value[],int maxWeight)
{
       
int dp[items+1][maxWeight+1];
       
/* dp[i][w] represents maximum value that can be attained if the maximum weight is w and
           items are chosen from 1...i */

       
/* dp[0][w] = 0 for all w because we have chosen 0 items */
       
int iter,w;
       
for(iter=0;iter<=maxWeight;iter++)
       
{
                dp
[0][iter]=0;
       
}
       
/* dp[i][0] = 0 for all w because maximum weight we can take is 0 */
       
for(iter=0;iter<=items;iter++)
       
{
                dp
[iter][0]=0;
       
}
       
for(iter=1;iter<=items;iter++)
       
{
               
for(w=0;w<=maxWeight;w++)
               
{
                        dp
[iter][w] = dp[iter-1][w]; /* If I do not take this item */
                       
if(w-weight[iter] >=0)
                       
{
                               
/* suppose if I take this item */
                                dp
[iter][w] = max(dp[iter][w] , dp[iter-1][w-weight[iter]]+value[iter]);
                       
}
               
}

       
}
       
return dp[items][maxWeight];
}
int main()
{
       
int items;
        scanf
("%d",&items);
       
int weight[items+1],value[items+1];
       
int iter;
       
for(iter=1;iter<=items;iter++)
       
{
                scanf
("%d%d",&weight[iter],&value[iter]);
       
}
       
int maxWeight;
        scanf
("%d",&maxWeight);
        printf
("Max value attained can be %d\n",Knapsack(items,weight,value,maxWeight));
}

Rough notes about the Algorithm - as implemented in the code above:

Firstly, input the total number of items, the weight and value of each item. Then input the
maximum weight (maxWeight). Lastly calculate the maximum value that can be attained using
Knapsack function.

Knapsack function – This function takes total number of items (items), weight of all the items
(weight), value of all the items (value) and the maximum weight (maxWeight) as arguments. It
returns the maximum value that can be attained.

Declare dp[items+1][maxWeight+1]. Where, dp[i][w] represents maximum value that can be attained if the maximum weight is w and items are chosen from 1...i.
dp[0][w] = 0 for all w because we have chosen 0 items. And, dp[i][0] = 0 for all w because maximum weight we can take is 0.
Recurrence: 
for i=1 to items
    for w=0 to maxWeight
        dp[i][w] = dp[i-1][w], if we do not tale item i. if w-weight[i] >=0, suppose we take this
        item then, dp[i][w] = max(dp[i][w] , dp[i-1][w-weight[i]]+value[i]). Where, max is a
        function that returns the maximum of the two arguments it takes.
     next
next
Return dp[items][maxWeight]
Related Tutorials (common examples of Dynamic Programming):

 Integer Knapsack problem

 An elementary problem, often used to introduce the concept of dynamic programming.
 Matrix Chain Multiplication

 Given a long chain of matrices of various sizes, how do you parenthesize them for the purpose of multiplication - how do you chose which ones to start multiplying first?

 Longest Common Subsequence 

 Given two strings, find the longest common sub sequence between them.