算法设计与分析 课件 5.4.3-动态规划-0-1背包问题-空间优化.pptx

;动态规划求解0-1背包问题时，空间复杂度为O(nc)。如果物品数n和背包容量c非常大时，算法对空间的需求也很大。;0;滚动数组

f[k][j]=max{vi+f[1-k][j-wi],f[1-k][j]}

k轮流取0,1;进一步，是否可以使用一维数组？;单选题。

如果使用一维数组的话，可以按照自左向右的顺序计算0-1背包问题吗？;单选题。

对0-1背包问题进行空间优化后，还可以利用f数组求解最优解吗？;0-1背包代表了一类问题，具有以下特征：

已知：

n个可选择的物品

每个物品有若干属性，比如重量和价值

一个容器（背包），有一个属性上的限制（容量）

问题：

在容器限制下，如何挑选物品（每个物品要么选要么不选）才能使得另一个属性达到极大值？

;书名;集装箱装载

;满背包问题

选择哪些物品刚好可以装满背包且价值最大

完全背包问题

每种物品有无限件

多重背包问题

第i种物品最多有Mi件可用

……;理解和掌握典型应用的主要特征，这样才能在不同的应用场景中，从现象到本质，抓住关键点，活学活用。;1.如果背包容量c和物品重量wi是小数，是否可以用动态规划求解0-1背包问题？

2.若c2n，则动态规划的时间复杂度为Ω(n2n)。与穷举法相比如何？

3.0-1背包问题中，f(i,j)表示背包容量为j、可选物品为i,i+1,…,n时问题的最优值。类似地，你能想到其他的最优值定义形式吗?