0
$\begingroup$

I am familiar with 0/1 knapsack problem. But if the following constraint is imposed... how do I solve the question?

  1. If you choose some item 'U' you won't be able to choose another item 'V'.

For example Items are given as [Name, Weight, Value]
Items are :
A 10 20
B 50 80
C 20 30
D 30 70
E 50 50

If you choose B then you cannot choose A.
If you choose E then you cannot choose C.
If you choose D then you cannot choose A.
In the similar way the constraints are given.

Please provide me some way to solve the above problem. Any help is highly appreciated.

$\endgroup$
4
  • $\begingroup$ Can you model it as an integer linear program? $\endgroup$ – Pål GD Jun 27 '20 at 8:30
  • 1
    $\begingroup$ If you choose B then you cannot choose A. - is that relationship symmetric? That is, if choose A first, then does that mean I still choose B second? Or does it also imply A and B can't be in the same knapsack regardless of selection order? $\endgroup$ – selbie Jun 27 '20 at 8:49
  • $\begingroup$ Yes the relation is symmetric. If A is chosen B cannot be chosen and vice versa. A and B cannot be in the same knapsack. $\endgroup$ – Anto Jun 27 '20 at 9:02
  • $\begingroup$ Please edit the mutuality of exclusion into your question. $\endgroup$ – greybeard Jun 28 '20 at 9:46
1
$\begingroup$

Standard dynamic programming approaches are likely not going to work for this problem, because the extra "this or that but not both" constraints destroy the overlapping subproblems property. So let's break out the sledgehammer.

You can easily encode this as a 0-1 integer linear programming problem and use an off-the-shelf solver. For the given example (and some maximum weight limit $W$), a suitable 0-1 ILP problem is:

maximize $20A + 80B + 30C + 70D + 50E$
subject to
$A, B, C, D, E \in \{0, 1\}$
$10A + 50B + 20C + 30D + 50E \le W$
$A + B \le 1$
$C + E \le 1$
$A + D \le 1$

Although, it is not obvious to me that an integer linear programming solver will take full advantage of the structure of the problem. So perhaps a more specialized solution may perform better in practice.

$\endgroup$
1
  • $\begingroup$ Thank you so much $\endgroup$ – Anto Jun 27 '20 at 19:10

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.