Why Capacity-1 in integer knapsack?

Question

The dynamic programming solution to the integer knapsack problem, For a knapsack of capacity C, and for n items, where ith item has the size Si and value Vi, is:

M(C)=max(M(C-1), M(C-Si)+Vi), where i goes from 1 to n

Here M is an array. M(C) denotes the maximum value of a knapsack of capacity C.

What is the use of M(C-1) in this relation? I mean the solution should just be this:

M(C)=max(M(C-Si)+Vi), where i goes from 1 to n

I think all the cases that M(C-1) covers are covered in M(C).

If I'm wrong, please give me an example situation.

Answer 1

I think you have to setup of the formula a bit confused - specifically, you've mixed up the capacity of the bag with a sub problem of n-1 items. Let's redefine a bit.

• Let P denote the problem, as represented by a list of n items.
• Further, let Pk represent the subproblem consisting of items at indices 1...k from the original problem, where 1 <= k <= n. Thus Pn is equivalent to P.
• For each item at index i, let Vi denote the value of that item and Si denote the size of that item.
• Let C be the capacity of the bag, C >= 0
• Let M(Pk, C) denote the optimal solution to the problem described by Pk with a bag of capacity C. M(Pk, C) returns the list of items included in the solution (and thus also returns the value of the optimal solution and the excess capacity in the bag).

For each item, we could either include it in the optimal solution, or not include it in the optimal solution. Clearly, the optimal solution is whichever of these two options is preferable. The only corner case to consider is if the item in question cannot fit in the bag. In this case we must exclude it.

We can rely on recursion to cover every item for us, thus have no need for iteration. Thus all together:

M(Pk,C) = if(Sk > C) M(P(k-1), C) else max(M(P(k-1),C), Vk + M(P(k-1),C-Sk))