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.
If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.
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. Time Complexity: O(nW) where n is the number of items and W is the capacity of knapsack. References: |

Algorithms > Dynamic Programming >