2
$\begingroup$

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?

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

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I see your point, thank you! But if I then have a lot of constraints like that one for different items? $\endgroup$ – Niko24 Oct 24 '17 at 8:17
  • $\begingroup$ @Niko24 Depending on the number of constraints you could try linear/integer programming. $\endgroup$ – fade2black Oct 24 '17 at 8:27
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.