We consider the integral (or 0/1) knapsack problem which is a modication of the fractional knapsack problem considered in Chapter 7. The problemisdenedasfollows. Problem6.1(0/1 Knapsack). We are given n objects and a knapsack. Object it has an integer weight wi and the knapsack has integer capacity,i.e., the maximum weight to fall items placed in the knapsack cannot exceed m. An object i is either placed into the knapsack or entirely omitted (no fractional part allowed), i.e., xi = 1 if the object is placed in the knapsack, and 0 otherwise. Iftheobjectiisplaced,thenaprotofpi earned. The objective istomaximizethetotalprotearnedsubjecttotheknapsackconstraint. We want to nd the optimal solution using Dynamic Programming. Thatiswewanttondthesolutionvectorx1,x2,...xn whichis0-1vector thatmaximizesthetotalprotearnedsubjecttotheknapsackconstraint. ANaiveSolution As usual, a simple, but the naive solution is to consider all possible subsets of objects(since each object can be either in the optimal solution or not) and take the subset that satises the knapsack capacity and maximizes the total prot. Since the number of subsets is 2n, this leads to exponential running time. DP, again, leads to a signicantly improved running time as explained below. Subproblems Thekey, again, for a correct recursive formulation is identifying the right subproblems. For this, as mentioned earlier, introducing auxiliary variables help. Lets introduce two new variables j,y as follows. Let KNAP(j,y) representtheproblem: maximizeP16i6j pixi;subjecttotheconstraintP16i6j wixi 6 y withthe(integral)requirementthat DYNAMICPROGRAMMING xi {0,1}, 1 6 i 6 j. The above is simply a restatement of the knapsack problem as an explicit maximization problem. The Knapsack problem is simplyKNAP(n,m). Notethatweassumeallweightsandmareintegers. Recursiveformulation Letfj(y)betheoptimalsolutiontoKNAP(j,y). Then,wecanwrite: fj(y) = max{fj1(y),fj1(ywj) + pj}. Thebasecasesare: f0(y) = 0 forall y > 0 and fi(y) = if y < 0. The correctness of the formulation The above formulation is correct because to compute f j(y)we need to look at only two choices: either the jth object is in the knapsack or not. If it is not included, then fj(y) = fj1(y), since no weight has been added. If it is included, then fj(y) = fj1(y wj) + pj, since we have to subtract the weight wj from the knapsack capacityandincludeitsprot. Thecorrectnessoftheformulation, as usual, can be established by induction. Againinductionimpliesthattheoptimalsubstructurepropertyholds. fj(y)should contain within itself the optimal solution to its subproblem(s) which are fj1(y) (in the rst case) and fj1(ywj) (in the second case). Of course, we take the maximum value of the two cases. DPalgorithm ADPalgorithmisstraightforwardfromtheaboveformulation. The desired optimal value is fn(m) which we compute in a bottom up manner. That is, we rst start from the base cases and compute f1(.),f2(.),... in this order. The time complexity is O(nm). Note that the running time depends on the number of objects as well as the (magnitude) of the (integer) capacity. Hence this is not a polynomial time algorithm, since the running time is not a polynomial function of the input size which is logm (since m can be represented using logm bits), but rather a polynomial function of m. Such a running time is referred to as pseudo-polynomial and the algorithm is called a pseudo-polynomial algorithm. Such algorithms are fast when the m is small; more importantly they can be converted to yield efcient polynomial time algorithms that giveanapproximatelyoptimalsolution.

Exercise6.10. Give peudocode of the DP algorithm(iterative) for computing the optimal prot for the knapsack problem based on the above formulation. Give also pseudocode of the recursive algorithm(with table lookup) for computing the optimal prot based on the above formulation. Analyze and show that the running time of both the algorithms are O(mn). Give an algorithm to output the optimal solution, i.e., the subset of objects that gives the optimal prot.