Knapsack Problem

0-1 Knapsack Problem

Knapsack Problem

• You have a knapsack that has capacity (weight) C.

• You have several items I1,…,In.

• Each item Ij has a weight wj and a benefit bj.

• You want to place a certain number of copies of each item Ij in the knapsack so that:

– The knapsack weight capacity is not exceeded and

– The total benefit is maximal.

Key question

• Suppose f(w) represents the maximal possible benefit of a knapsack with weight w.

• We want to find (in the example) f(5).

• Is there anything we can say about f(w) for arbitrary w?

Key observation

• To fill a knapsack with items of weight w, we must have added items into the knapsack in some order.

• Suppose the last such item was Ij with weight wi and benefit bi.

• Consider the knapsack with weight (w- wi). Clearly, we chose to add Ij to this knapsack because of all items with weight wi or less, Ij had the max benefit bi.

Key observation

• Thus, f(w) = MAX { bj + f(w-wj) | Ij is an item}.

• This gives rise to an immediate recursive algorithm to determine how to fill a knapsack.

Example

f(0), f(1)

• f(0) = 0. Why? The knapsack with capacity 0 can have nothing in it.

• f(1) = 0. There is no item with weight 1.

f(2)

• f(2) = 60. There is only one item with weight 60.

• Choose A.

f(3)

• f(3) = MAX { bj + f(w-wj) | Ij is an item}.

= MAX { 60+f(3-2), 75 + f(3-3)}

= MAX { 60 + 0, 75 + 0 }

= 75.

Choose B.

f(4)

• f(4) = MAX { bj + f(w-wj) | Ij is an item}.

= MAX { 60 + f(4-2), 75 + f(4-3), 90+f(4-4)}

= MAX { 60 + 60, 75 + f(1), 90 + f(0)}

= MAX { 120, 75, 90}

=120.

Choose A.

f(5)

• f(5) = MAX { bj + f(w-wj) | Ij is an item}.

= MAX { 60 + f(5-2), 75 + f(5-3), 90+f(5-4)}

= MAX { 60 + f(3), 75 + f(2), 90 + f(1)}

= MAX { 60 + 75, 75 + 60, 90+0}

= 135.

Choose A or B.

Result

• Optimal knapsack weight is 135.

• Two possible optimal solutions:

– Choose A during computation of f(5). Choose B in computation of f(3).

– Choose B during computation of f(5). Choose A in computation of f(2).

• Both solutions coincide. Take A and B.

Knapsack Problem Variants

• 0/1 Knapsack problem: Similar to the knapsack problem except that for each item, only 1 copy is available (not an unlimited number as we have been assuming so far).

• Fractional knapsack problem: You can take a fractional number of items. Has the same constraint as 0/1 knapsack. Can solve using a greedy algorithm.

0/1 Knapsack

• f[j,w] = best solution having weight exactly w after considering j elements

• If j >= C: f[j,w] = f[j-1,w]

• Otherwise: f[j,w] =

• MAXremaining items {

– f[j-1,w],

– f[j-1,w-wj]+bj }

0/1 Knapsack Algorithm

For w = 0 to C do f[w]=0; (* initialize *)

For j=1 to n do

for w=C downto wj do

if f[w-wj] + bj > f[w] then

f[w] = f[w-wj] + bj


O(n.C) algorithm

Fractional knapsack

• Much easier

• For item Ij, let rj = bj/wj. This gives you the benefit per measure of weight.

• Sort the items in descending order of rj

• Pack the knapsack by putting as many of each item as you can walking down the sorted list.

----------------------------------------------------------------------------------------------------------------------------

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).

A simple solution is to consider all subsets of items and calculate the total weight and value of all subsets. Consider the only subsets whose total weight is smaller than W. From all such subsets, pick the maximum value subset.

1) Optimal Substructure:

To consider all subsets of items, there can be two cases for every item: (1) the item is included in the optimal subset, (2) not included in the optimal set.

Therefore, the maximum value that can be obtained from n items is max of following two values.

1) Maximum value obtained by n-1 items and W weight (excluding nth item).

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

If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.

2) Overlapping Subproblems

Following is recursive implementation that simply follows the recursive structure mentioned above.

/* A Naive recursive implementation of 0-1 Knapsack problem */

#include<stdio.h>

// A utility function that returns maximum of two integers

int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W

int knapSack(int W, int wt[], int val[], int n)

{

// Base Case

if (n == 0 || W == 0)

return 0;

// If weight of the nth item is more than Knapsack capacity W, then

// this item cannot be included in the optimal solution

if (wt[n-1] > W)

return knapSack(W, wt, val, n-1);

// Return the maximum of two cases: (1) nth item included (2) not included

else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),

knapSack(W, wt, val, n-1)

);

}

// Driver program to test above function

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;

}

It should be noted that the above function computes the same subproblems again and again. See the following recursion tree, K(1, 1) is being evaluated twice. Time complexity of this naive recursive solution is exponential (2^n).

In the following recursion tree, K() refers to knapSack(). The two parameters indicated in the following recursion tree are n and W. The recursion tree is for following sample inputs. wt[] = {1, 1, 1}, W = 2, val[] = {10, 20, 30} K(3, 2) ---------> K(n, W) / \ / \ K(2,2) K(2,1) / \ / \ / \ / \ K(1,2) K(1,1) K(1,1) K(1,0) / \ / \ / \ / \ / \ / \ K(0,2) K(0,1) K(0,1) K(0,0) K(0,1) K(0,0) Recursion tree for Knapsack capacity 2 units and 3 items of 1 unit weight.

Since suproblems are evaluated again, this problem has Overlapping Subprolems property. So the 0-1 Knapsack problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array K[][] in bottom up manner. Following is Dynamic Programming based implementation.

// A Dynamic Programming based solution for 0-1 Knapsack problem

#include<stdio.h>

// A utility function that returns maximum of two integers

int max(int a, int b) { return (a > b)? a : b; }

// 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] = 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;

}