Modification of dynamic programming for a knapsack problem

Question

We have the following recursive function for the dynamic programming problem for a knapsack problem:

\begin{align} V(i,w)=&max[ V(i-1,w), v_i +V(i-1,w-w_i)], \quad 1\leq i \leq n, 0\leq w \leq W \\ \end{align} and $V(0,w)=0$.

But is it possible to add a constraint on the items to this function? If we for instance only are allowed to put one of the items 1 or 2 in: $x_1 + x_2 \leq 1$? And how to do this?

• fade2black: Do you want to find the optimum solution which includes either item 1 or 2 (not both)?
• fade2black: Or do you want to express this constraint in LP terms?

Answer 1

Apply the golden rule of DP (that is how I name it), namely, adding another parameter to the subproblems/object function when there is an extra condition or dimension of freedom. This rule is simple and powerful, yet it can be overlooked by DP beginners and sometimes experienced guys.

In this particular question, instead of $V(i,w)$, define $V(i,w,c)$, where $V(i,w,0)$ means no item 1 and no item 2, $V(i,w,1)$ means one item, and $V(i,w,2)$ means one item 2. Rewrite the recurrence relation accordingly. Compute the values either recursively or iteratively with memoization. Select the desired result among possible candidates.

This answer can be seen as a formalization of @fade2black's answer, although I had/have been calling/using the golden rules too many times in my DP adventure.

Answer 2

One possible way is to call the the DP algorithm first without the item 1 and then without the item 2. The maximum one is the optimal solution.

• Niko24: I see your point, thank you! But if I then have a lot of constraints like that one for different items?
• fade2black: @Niko24 Depending on the number of constraints you could try linear/integer programming.

Answer 3

No, if you want to allow an arbitrary number of those constraints. The constraints that you would like to add make the problem strongly NP-hard, because they can encode the independent set problem. In particular, your problem with constraints cannot have a pseudo-polynomial time algorithm (unless P = NP).