While standard knapsack problem can be solved by dynamic programming, I am trying to twist the problem a bit to clear my concept, however I found it maybe harder than I thought.
Original knapsack problem is that given a knapsack with size W
, and a list of items which weight w[i]
and has a value v[i]
, find the subset of items which can fit in the knapsack with highest total value.
To my understanding, this can be done by O(Wn)
with dynamic programming, where n
is the number of items.
Now if I try to add m
constrains, each of them is a pair of items which can only be picked mutual exclusively (i.e. if there exist a constrain of item A and item B, then I can only take either one of them but not both)
Under such constrains, can this problem still be solved by dynamic programming in O(Wn)
?