CODEWITHSUNDEEP
algorithmdynamic-programmingknapsack-problem
Daniel.V
Daniel.V

Reputation: 2492

Knapsack with one additional constraint

This is the old and famous knapsack problem : Knapsack Problem
Here I have Knapsack problem with one constraint.
I have Knapsack with size W = 100000000 and N = 100 items I wrote the dynamic solution for it the Complexity of my algorithm is O(100000000*100) and this is too big in both time and space but there is one condition here that either W ≤ 50000 or max 1≤ i ≤ n Vi ≤ 500. so if my Knapsack size is more than 50000 my maximum value of items is limited.
So now I wonder how can I reduce the time Complexity of my algorithm with this condition I thought Knapsack problem depends on the size of knapsack and the number of items so how the value of items can change the change my algorithm?

Upvotes: -1

Views: 985

Answers (1)

amit
amit

Reputation: 178421

Instead of creating a table of size W*n, where each entry D[x][i] indicates the best value (highest) you can get with at most x weight using the first i items, use the table where now D[x][i] is the minimal weight needed to get to value of x, using the first i elements:

D(0,i) = 0                i>0
D(x,0) = infinity         x > 0
D(x,i) = infinity         x<0 or i<0
D(x,i) = min{ D(x,i-1), D(x-value[i],i-1) + weight[i])

When you are done, find max{ x | D(x,n) <= W) } - this is the highest value you can get, using at most W weight, and is done by a linear scan of the last line of the DP matrix.

Checking which variation you need is done by a single scan of the data.

Upvotes: 2

Related Questions