CODEWITHSUNDEEP
algorithmoptimizationdynamic-programming
colis
colis

Reputation: 23

Knapsack variation in Dynamic Programming

I'm trying to solve this exercise: we are given n items, where each has a given nonnegative weigth w1,w2,...,wn and value v1,v2,...,vn, and a knapsack with max weigth capacity W. I have to find a subset S of maximum value, subject to two restricions: 1) the total weight of the set should not exceed W; 2) I can't take objects with consecutive index.

For example, with n = 10, possible solutions are {1, 4, 6, 9}, {2, 4, 10} o {1, 10}.

How can I build a correct recurrence?

Upvotes: 2

Views: 1684

Answers (1)

amit
amit

Reputation: 178531

Recall that the knapsack recursive formula used for the DP solution is:

D(i,w) = max { D(i-1,w) , D(i-1,w-weight[i]) + value[i] }

In your modified problem, if you chose to take i - you cannot take i-1, resulting in the modification of:

D(i,w) = max { D(i-1,w) , D(i-2,w-weight[i]) + value[i] }
                              ^
                          note here 
                       i-2 instead of i-1

Similar to classic knapsack, it is also an exhaustive search - and thus provides optimal solution for the same reasons.
The idea is given that you have decided to chose i - you cannot chose i-1, so find the optimal solution that uses at most the item i-2. (no change from the original if you decided to exclude i)

Upvotes: 5

Related Questions