# Knapsack problem with a constraint

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.

• Can you model it as an integer linear program? Jun 27, 2020 at 8:30
• 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? Jun 27, 2020 at 8:49
• 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.
– Anto
Jun 27, 2020 at 9:02
• Please edit the mutuality of exclusion into your question. Jun 28, 2020 at 9:46

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.

• Thank you so much
– Anto
Jun 27, 2020 at 19:10