[Solved]: Integer Knapsack Problem - No duplicates Allowed

Problem Detail: 

In the bounded Integer Knapsack problem, we are given N items of sizes S1 through SN, having values V1 through VN. The problem requires us to find the maximum value that can be attained for a given capacity C, provided we cannot use an already used item twice.

In their book, Introduction to Algorithms, the authors have mentioned that for Dynamic programming to be applicable we MUST have "independent" subproblems. That is, the solution to one subproblem should not affect another subproblem. They have illustrated this through the "Longest-Path-Problem" in which they mention that once we solve a subproblem of finding the longest path from 'A' to 'B', for solving another subproblem, we would not be able to use the vertices used in the longest path from 'A' to 'B' and hence the subproblems are not independent.

Doesn't the same argument apply here as well - If we solve a subproblem of filling a smaller knapsack of capacity c < C, we cannot use the items used in filling 'c', in solving other subproblems.

I am new to dynamic programming - apologies if my question appears to be stupid.

Thanks.

Asked By : Abhigyan Mehra

Answered By : hengxin

You are right about "independence" between subproblems. Therefore, you use the new subproblems (wiki) by introducing another variable $i$, meaning using the items up to $i$:

Define $V[i,s]$ to be the maximum value ($V$) that can be attained with size less than or equal to $s$ using items up to $i$ (the first $i$ items).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42624