多重背包问题为什么不能优化为一维
假设我们有一个体积为6的背包,我们有如下物品:
1 2 3(体积1,价值2,数量3)
3 1 1(体积3,价值1,数量1)
当我们更新dp[j] = max(d[j],d[j-v[i]+w[i])的时候
更新第一个物品:
d[1] = 2;
d[2] = 4;
…
d[6] = [12];
原因在于,我们并不知道,d[j-v[i]]里包含了多少个当前物品,
我们无法知道它的重量是怎样进行分配的。
换句话说,就是,我们一维数组只能记录最优解,无法记录最优解的取得条件。