## 4.5 The Greedy Approach versus Dynamic Programming: The Knapsack Problem The greedy approach and dynamic programming are two ways to solve optimization problems. Often a problem can be solved using either approach. For example, the Single-Source Shortest Paths problem is solved using dynamic programming in [Algorithm 3.3](LiB0026.html#277) and is solved using the greedy approach in [Algorithm 4.3](LiB0034.html#403). However, the dynamic programming algorithm is overkill in that it produces the shortest paths from all sources. There is no way to modify the algorithm to produce more efficiently only shortest paths from a single source because the entire array *D* is needed regardless. Therefore, the dynamic programming approach yields a Θ (*n*3) algorithm for the problem, whereas the greedy approach yields a Θ (*n*2) algorithm. Often when the greedy approach solves a problem, the result is a simpler, more efficient algorithm. On the other hand, it is usually more difficult to determine whether a greedy algorithm always produces an optimal solution. As the Change problem shows, not all greedy algorithms do. A proof is needed to show that a particular greedy algorithm always produces an optimal solution, whereas a counterexample is needed to show that it does not. Recall that in the case of dynamic programming we need only determine whether the principle of optimality applies. To illuminate further the differences between the two approaches, we will present two very similar problems, the 0–1 Knapsack problem and the Fractional Knapsack problem. We will develop a greedy algorithm that successfully solves the Fractional Knapsack problem but fails in the case of the 0–1 Knapsack problem. Then we will successfully solve the 0–1 Knapsack problem using dynamic programming. ### 4.5.1 A Greedy Approach to the 0-1 Knapsack Problem An example of this problem concerns a thief breaking into a jewelry store carrying a knapsack. The knapsack will break if the total weight of the items stolen exceeds some maximum weight *W.* Each item has a value and a weight. The thief's dilemma is to maximize the total value of the items while not making the total weight exceed *W.* This problem is called the 0–1 Knapsack problem. It can be formalized as follows. Suppose there are *n* items. Let  where *wi*, *pi*, and *W* are positive integers. Determine a subset *A* and *S* such that  The brute-force solution is to consider all subsets of the *n* items; discard those subsets whose total weight exceeds *W*; and, of those remaining, take one with maximum total profit. Example A.10 in [Appendix A](LiB0093.html#1281) shows that there are 2*n* subsets of a set containing *n* items. Therefore, the brute-force algorithm is exponential-time. An obvious greedy strategy is to steal the items with the largest profit first; that is, steal them in nonincreasing order according to profit. This strategy, however, would not work very well if the most profitable item had a large weight in comparison to its profit. For example, suppose we had three items, the first weighing 25 pounds and having a profit of $10, and the second and third each weighing 10 pounds and having a profit of $9. If the capacity *W* of the knapsack was 30 pounds, this greedy strategy would yield only a profit of $10, whereas the optimal solution is $18. Another obvious greedy strategy is to steal the lightest items first. This strategy fails badly when the light items have small profits compared with their weights. To avoid the pitfalls of the previous two greedy algorithms, a more sophisticated greedy strategy is to steal the items with the largest profit per unit weight first. That is, we order the items in nonincreasing order according to profit per unit weight, and select them in sequence. An item is put in the knapsack if its weight does not bring the total weight above *W.* This approach is illustrated in [Figure 4.13](#ch04fig13). In that figure, the weight and profit for each item are listed by the item, and the value of *W*, which is 30, is listed in the knapsack. We have the following profits per unit weight:  [](fig4-13_0.jpg) Figure 4.13: A greedy solution and an optimal solution to the 0-1 Knapsack problem. Ordering the items by profit per unit weight yields > *item*1, *item*3, *item*2 As can be seen in the figure, this greedy approach chooses *item*1 and *item*3, resulting in a total profit of $190, whereas the optimal solution is to choose *item*2 and *item*3, resulting in a total profit of $200. The problem is that after *item*1 and *item*3 are chosen, there are 5 pounds of capacity left, but it is wasted because *item*2 weighs 10 pounds. Even this more sophisticated greedy algorithm does not solve the 0–1 Knapsack problem. ### 4.5.2 A Greedy Approach to the Fractional Knapsack Problem In the Fractional Knapsack problem, the thief does not have to steal all of an item, but rather can take any fraction of the item. We can think of the items in the 0-1 Knapsack problem as being gold or silver ingots and the items in the Fractional Knapsack problem as being bags of gold or silver dust. Suppose we have the items in [Figure 4.13](#ch04fig13). If our greedy strategy is again to choose the items with the largest profit per unit weight first, all of *item*1 and *item*3 will be taken as before. However, we can use the 5 pounds of remaining capacity to take 5/10 of *item*2. Our total profit is  Our greedy algorithm never wastes any capacity in the Fractional Knapsack problem as it does in the 0–1 Knapsack problem. As a result, it always yields an optimal solution. You are asked to prove this in the exercises. ### 4.5.3 A Dynamic Programming Approach to the 0-1 Knapsack Problem If we can show that the principle of optimality applies, we can solve the 0–1 Knapsack problem using dynamic programming. To that end, let *A* be an optimal subset of the *n* items. There are two cases: either *A* contains *itemn* or it does not. If *A* does not contain *itemn*, *A* is equal to an optimal subset of the first *n* - 1 items. If *A* does not contain *itemn*, the total profit of the items in *A* is equal to *pn* plus the optimal profit obtained when the items can be chosen from the first *n* -1 items under the restriction that the total weight cannot exceed *W*-*wn.* Therefore, the principle of optimality applies. The result just obtained can be generalized as follows. If for *i*>0 and *w*>0, we let *P\[i\]\[w\]* be the optimal profit obtained when choosing items only from the first *i* items under the restriction that the total weight cannot exceed *w*,  The maximum profit is equal to *P\[n\]\[W\].* We can determine this value using a two-dimensional array *P* whose rows are indexed from 0 to *n* and whose columns are indexed from 0 to *W.* We compute the values in the rows of the array in sequence using the previous expression for *P\[i\]\[w\]*. The values of *P\[0\]\[w\]* and *P\[i\]*\[0\] are set to 0. You are asked to actually write the algorithm in the exercises. It is straightforward that the number of array entries computed is  ### 4.5.4 A Refinement of the Dynamic Programming Algorithm for the 0-1 Knapsack Problem The fact that the previous expression for the number of array entries computed is linear in *n* can mislead one into thinking that the algorithm is efficient for all instances containing *n* items. This is not the case. The other term in that expression is *W*, and there is no relationship between *n* and *W.* Therefore, for a given *n*, we can create instances with arbitrarily large running times by taking arbitrarily large values of *W.* For example, the number of entries computed is in Θ (*n* ×*n*!) if *W* equals *n*!. If *n* = 20 and *W* = 20!, the algorithm will take thousands of years to run on a modern-day computer. When *W* is extremely large in comparison with *n*, this algorithm is worse than the bruteforce algorithm that simply considers all subsets. The algorithm can be improved so that the worst-case number of entries computed is in Θ (2*n*). With this improvement, it never performs worse than the brute-force algorithm and often performs much better. The improvement is based on the fact that it is not necessary to determine the entries in the *i*th row for every *w* between 1 and *W.* Rather, in the *n*th row we need only determine *P\[n\]\[W\].* Therefore, the only entries needed in the (*n* -1)st row are the ones needed to compute *P\[n\]\[W\].* Because  the only entries needed in the (*n* -1)st row are  We continue to work backward from *n* to determine which entries are needed. That is, after we determine which entries are needed in the *i*th row, we determine which entries are needed in the (*i*-1)st row using the fact that  We stop when *n* = 1 or *w* ≤ 0. After determining the entries needed, we do the computations starting with the first row. The following example illustrates this method. Example 4.9****Suppose we have the items in [Figure 4.13](#ch04fig13) and *W* = 30. First we determine which entries are needed in each row. Determine entries needed in row 3: We need  Determine entries needed in row 2: To compute *P* \[3\] \[30\], we need  Determine entries needed in row 1: To compute *P* \[2\] \[30\], we need  To compute *P*\[2\]\[10\], we need  Next we do the computations. Compute row 1:  Therefore,  Compute row 2:   Compute row 3:  **** This version of the algorithm computes only seven entries, whereas the original version would have computed (3)(30) = 90 entries. Let's determine how efficient this version is in the worst case. Notice that we compute at most 2*i* entries in the (*n*-*i*)th row. Therefore, at most the total number of entries computed is  This equality is obtained in Example A.3 in [Appendix A](LiB0093.html#1281). It is left as an exercise to show that the following is an instance for which about 2*n* entries are computed (the profits can have any values):  Combining these two results, we can conclude that the worst-case number of entries computed is in  The previous bound is in terms of only *n.* Let's also obtain a bound in terms of *n* and *W* combined. We know that the number of entries computed is in *O*(*nW*), but perhaps this version avoids ever reaching this bound. This is not the case. In the exercises you will show that if *n* = *W*+1 and *wi* = 1 for all *i*, then the total number of entries computed is about  The first equality is obtained in Example A.1 in [Appendix A](LiB0093.html#1281), and the second derives from the fact that *n* = *W*+1 in this instance. Therefore, this bound is reached for arbitrarily large values of *n* and *W*, which means the worst-case number of entries computed is in  Combining our two results, the worst-case number of entries computed is in  We do not need to create the entire array to implement the algorithm. Instead, we can store just the entries that are needed. The entire array exists only implicitly. If the algorithm is implemented in this manner, the worst-case memory usage has these same bounds. We could write a divide-and-conquer algorithm using the expression for *P\[i\]\[w\]* that was used to develop the dynamic programming algorithm. For this algorithm the worst-case number of entries computed is also in Θ(2*n*). The main advantage of the dynamic programming algorithm is the additional bound in terms of *nW.* The divide-and-conquer algorithm does not have this bound. Indeed, this bound is obtained because of the fundamental difference between dynamic programming and divide-and-conquer. That is, dynamic programming does not process the same instance more than once. The bound in terms of *nW* is very significant when *W* is not large in comparison with *n.* As is the case for the Traveling Salesperson problem, no one has ever found an algorithm for the 0–1 Knapsack problem whose worst-case time complexity is better than exponential, yet no one has proven that such an algorithm is not possible. Such problems are the focus of [Chapter 9](LiB0074.html#880).