状态转移方程3.

种物品只有两种选择装入背包或不装入背包。

如何选择装入背包的物品使装入背包中的物品的总价值最大

[NOIP2005

dp[i][j]dp[i−1][j−c[i]]w[i]。

不装第

i−1

dp[i][j]dp[i−1][j]。

此时取这两者中的较大值作为当前背包的价值状态转移方程为

dp[i][j]

dp[i][j]max(dp[i−1][j],dp[i−1][j−c[i]]w[i])

0/1

空间优化技术。

动态规划的状态方程通常是二维即以上占用了太多空间用滚动数组可以

极大程度上

dp[i][j]max(dp[i−1][j],dp[i−1][j−c[i]]w[i])

dp[i][]

它们占用的空间用新的一行覆盖已经无用的一行只需要两行就够了。

这就是“滚动”的含义。

6.1

它表示引用传递使用传入的实参而不是重新创建一个新变量来代表实参这是

void

由于复用了空间从而覆盖了之前的计算结果数组中的值没有固定的实际含义难以理解通常都是先写出常规的动态规划再使用滚动数组进行优化。

还是因为复用了空间导致只留下最后一次计算的状态无法从数组中看出具体的方案。

三、总结