# Modification of dynamic programming for a knapsack problem

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?

• Do you want to find the optimum solution which includes either item 1 or 2 (not both)? – fade2black Oct 23 '17 at 22:44
• Or do you want to express this constraint in LP terms? – fade2black Oct 23 '17 at 22:48

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.