Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Knapsack with mutually exclusive items

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)?

like image 591
shole Avatar asked Jul 26 '16 06:07

shole


1 Answers

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 nth 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.

like image 103
Abhishek Bansal Avatar answered Oct 06 '22 01:10

Abhishek Bansal