Dynamic-Programming Solution to the 0-1 Knapsack Problem

Problem Statement 0-1 Knapsack problem
Input :
There are n items, and each item has a value:

• value vi   (non negative)
• size or weight wi (non negative and integral )
• Capicity W (non negative and integer)

Output:
  Select a subset  S ⊆ {1,2,3,....n}

• that maximizes ∑ vi 
• subject to max value&sum wi ≤ W

 Sometimes you may hear a cheesy problem a thief robbing a store and can carry a maximal weight of W into their knapsack. There are n items and ith  item weigh wi and is worth vi dollars. What items should thief take?d

There are two versions of problem:

• Fractional knapsack problem   
• 0-1 knapsack problem   

Comparing Fractional Knapsack vs 0-1 Knapsack

Fractional knapsack problem
The setup is same, but the thief can take fractions of items, meaning that the items can be broken into smaller pieces so that thief may decide to carry only a fraction of xi of item i, where 0 ≤ xi ≤ 1.

Exhibit greedy choice property.

•          Greedy algorithm exists.
•          Exhibit optimal substructure property.

0-1 knapsack problem
The setup is the same, but the items may not be broken into smaller pieces, so thief may decide either to take an item or to leave it (binary choice), but may not take a fraction of an item.

So, the above problem statement holds for 0-1 knapsack problem as we are referring to integral wi.

• Exhibit No greedy choice property. No greedy algorithm exists.
• Exhibit optimal substructure property.
• Only dynamic programming algorithm exists.

Brute force method
Since there are n items, there are 2ⁿ possible combinations of items.
We go through all combinations and find the one with maximum value and with total weight less or equal to W
Running time will be O(2ⁿ)

Dynamic-Programming Solution to the 0-1 Knapsack Problem
The naive way to solve this problem is to cycle through all 2ⁿ subsets of the n items and pick the subset with a legal weight that maximizes the value of the knapsack. But, we can find a dynamic programming algorithm that will USUALLY do better than this brute force technique.

Now lets see the dynamic programming route.
 

Let S be the optimal solution S.
Let n be the last item in an optimal solution S for W pounds.

Defining the sub problem - try 1
Let’s try this:
If items are labeled 1..n, then a subproblem would be to find an optimal solution for
Sk = {items labeled 1, 2, .. k}

If items are labeled 1..n, then a subproblem would be to find an optimal solution for Sk = {items labeled 1, 2, .. k}

This is a reasonable subproblem definition.
The question is: can we describe the final solution (Sn ) in terms of subproblems (Sk)?
Unfortunately, we can’t do that.


Consider the following items:
n=5, W=20

i	Item	wi	vi or bi
1	I0	2	3
2	I1	4	5
3	I2	5	8
4	I3	3	4
5	I4	9	10

Consider W= 20. Lets try to take 1st 4 items, ie. S4 and 1st 5 items - S5.

So, clearly S4 is not sub part of S5, hence our solution is flawed.

Defining the sub problem try 2
The subproblem then will be to compute V[i,x], i.e., to find an optimal solution for Sk = {items labeled 1, 2, .. i} in a knapsack of size x. Now we have to derive V[i,x].

Case 1: Suppose n ∉ S (n not in S)
Then S must be optimal solution with first n-1 Items Ii.
Maximum value obtained by n-1 items and W weight (excluding nth item).

Case2 : Suppose n ∈ S (n is indeed in S)
If we remove the last item n, then S - {n} is the optimal solution w.r.t. the 1st n-1 items and capacitiy W - wn.

Let V_ix = value of the best solution on that :

1. uses only the first i items
2. has total size ≤ x

Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).

So, we have to keep track of how many items we have used and the total size.

for i ∈ {1,2,3,...n}  and any x

V_ix = MAX ( V_(i-1)x  , vi + V_{(i-1)x- wi} ) OR

So, in case 1, wi>x. Item i can’t be part of the solution, since if it was, the total weight would be > w, which is unacceptable.
In case 2, wi ≤ x. Then the item i can be in the solution, and we choose the case with greater value.

One quick edge case, if wi > x, then we cant use it, and we have Vix = V(i-1)x , we are using case 1.

Step2 - The sub problem
Recall W and weight wi are integers, therefore in the worst case each case of residual capacities x ∈ {0,1,2,...,W).

Let A = 2-D array - as we have to keep track of 2 things - what items we have to use and what capacity we have to respect.

//The corner case where we don't take item at all, 
//i.e. i=0, and A[item,x] = 0 where item=0
for x = 0 to W
     A[0,x] = 0

FOR i=1 to n
    DO c[i, 0] = 0
        FOR x=0 TO W
            A[i,x] = max ( A[i-1,x],A[i-1,x-wi]+vi )

Running time
Note on run time: Clearly the run time of this algorithm is O(nW), based on the nested loop structure and the simple operation inside of both loops. When comparing this with the previous O(2ⁿ), we find that depending on W, either the dynamic programming algorithm is more efficient or the brute force algorithm could be more efficient. (For example, for n=5, W=100000, brute force is preferable, but for n=30 and W=1000, the dynamic programming solution is preferable.)

Example
Lets take the example now.
Input:
n=4, W=5
 Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)

Solution
Lets denote sub problem solution weight by w, instead of x.
Case 0 - When we have no items, so w=0

case 1 - When we have w=0, so we have to select no items

After discussing the corner cases, lets now solve the actual problem.

Knapsack in java

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
   int i, w;
   int K[n+1][W+1];
 
   // Build table K[][] in bottom up manner
   for (i = 0; i <= n; i++)
   {
       for (w = 0; w <= W; w++)
       {
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (wt[i-1] <= w)
                 K[i][w] = Math.max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }
 
   return K[n][W];
}
 
int main()
{
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int  W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    printf("%d", knapSack(W, wt, val, n));
    return 0;
}

Thanks