Knapsack with items to consider constraint

Question

I have items I1, I2, I3, I4 with weights W1...W4 and Values V1...V4. I want to maximize values with minimum weights. This is a traditional Knapsack. However there is small constraint some items cannot go together. So lets say I2 and I3 cannot go together. Can anyone provide a dynamic programming solution or any other solution for the same.

Answer 1

With this constraint, the problem becomes strongly (as opposed to discrete knapsack, which is only weakly NP-hard) NP-hard. Suppose all your items have weight 1 and value 1.

Deciding whether you can achieve value k (assuming knapsack capacity >= k) is equivalent to finding k items that have no constraint between them. This is a known NP-hard problem: independent set.

This might be easier if you have some additional knowledge about the nature of the constraints.