找到你要的答案

Q:Knapsack with one additional constraint

Q:一次约束背包

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?

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?

answer1: 回答1:

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.

而不是创建一个表的大小w * N,其中每一个条目D [ i ]表示最佳值(最高),你可以得到在大多数X重量使用第一个我的项目,使用表,现在D [ x ] [ i ]是最小的重量需要获得x值,使用第一个I元素:

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

当你完成的时候,发现最大{ x | D(x,n)& lt;= W)} -这是你能得到的最高价值,在重量和使用,是通过一个线性的DP矩阵的最后一行扫描。

检查您需要的变化是通过一个单一的扫描数据。

algorithm  dynamic-programming  knapsack-problem