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)
?
Assumption: Each element is included in atmost one constraint.
For the usual Knapsack problem, the optimal substructure that the problem exhibits is as follows:
For each item there can be two cases:
1. The item is included in the solution
2. The item not included in the solution.
Hence, the optimal solution for n
items is given by max of following two values.
1. Maximum value obtained by n-1
items and W
weight.
2. v_n
+ maximum value obtained by n-1
items and W-w_n
weight.
Now if we add the constraint that either of n
th or (n-1)
th item can exist in the solution, then the optimal solution for n
items is given by max of following three values.
1. Maximum value obtained by n-2
items and W
weight.
2. v_n
+ maximum value obtained by n-2
items and W-w_n
weight.
3. v_(n-1)
+ maximum value obtained by n-2
items and W-w_(n-1)
weight.
So we treat each pair of elements in the constraint as a single element and execute the dynamic programming algorithm in O(Wn)
time.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With