Knapsack problem with a constraint

Question

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.

Answer 1

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.