Question

Recall the dynamic programming algorithm we saw in class for solving the 0/1 knapsack problem for n objects with a knapsack capacity of K. In particular, we characterized our recurrence OPT(j, W) to be following quantity:

OPT(j, W) := The maximum profit that can be obtained when selecting from objects 1, 2, . . . , j with a knapsack capacity of W , where (after filling in our dynamic programming table), we return the value stored at OPT(n, K) as our final answer.

In this problem, we’ll consider an alternate dynamic programming approach for solving 0/1 knapsack.

a/ Suppose we now define our recurrence in the following way: OPT(j, R) := The smallest capacity that permits us to earn a total revenue of exactly R when selecting from objects 1, 2, . . . , j. Give a formal definition for OPT(j, R), defined as a recurrence that characterizes the quantity in terms of smaller subproblems. You may assume all weights and prices are positive integers. Be sure to define all necessary base cases, and give a brief justification for why your recurrence is correct.

b/ Using your recurrence from part (a), describe both (i) the order in which the algorithm should fill the dynamic programming table, and (ii) how, once filled in, the table can be used to return the final answer. Remember, we are still looking to return the maximum profit that can be obtained when selecting from all items (in other words, only the algorithm has changed, not the problem definition)

c/ What is the run time of your algorithm? For what kind of inputs might it be better to use this algorithm instead of our original approach? Briefly justify your answer.

Answer 1

(a) Let OPT(j, R) represent the smallest capacity of the knapsack to earn a total revenue of exactly R when selecting from objects from 1 to j.

Let Vj represent value of the jth object and Wj the weight of the jth object.

So now let us suppose we know all answers till j-1. Now for finding answer for j,R we have two choices-

1. Do not take the jth object. In this case answer is same as answer of j-1,R
2. Take the jth object. Now the answer will be Wj more than the ans for R-Vj since we want R as the revenue after taking this object of value Vj. Also note that if R < Vj we cannot take this object.

So here is the final recurrence

So if R >= Vj

OPT(j, R) = min(OPT(j - 1, R), OPT(j - 1, R - Vj) + Wj)

otherwise if R < Vj

  OPT(j, R) = OPT(j - 1, R)

and OPT(j, 0) = 0 for all j = 0 to n. This is beacuse 0 value requires 0 capacity.

and OPT(0, R) = infinite for all R > 0. This is because without selecting any element it's impossible to generate a non 0 revenue. For practical purposes we will take infinite as a very large number like INT_MAX in cpp.

(b) Now we need to create a table with rows indexed from 0 to n representing j and columns labelled from 0 to MAXR representing revenue R. But what is MAXR? What is the maximum revenue we can generate ignoring the constraint? It is the sum of all values of all objects because we cannot generate more than that for sure.

(i) Now to fill the table we will first fill in the first column, R = 0 with 0s and the first row, j = 0, R > 0 with INF(a very large value representing infinity). Now we will start filling the table in top down manner taking the minimum of value just above it and the value Vj cell left of the cell immidiately above it + Wj.

(ii) Now once the table is filled we can get the answer by iterating in the last row j = n and finding the largest R where the cell contains a value <= K (the given capacity). This R is the max revenue that can be obtained.

(c) Runtime of this lagorithm is O(n*(MAXR)) where MAXR is the sum of all values of the objects. This is because we fill the table one cell at a time and the table is of size n*MAXR. We can use this algorithm if the weights are very large but the values of the objects are small.