CODEWITHSUNDEEP
algorithmdynamic-programming
shole
shole

Reputation: 4084

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

Upvotes: 8

Views: 1652

Answers (1)

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

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.

Upvotes: 6

Related Questions