注意到原来每次f[i][v]只用了一次,所以现在f[v]相当于原来的f[v],
上次循环保存的f[v]相当于原来的f[i-1][v]
如果从0做到V的话,没有重复限制,会从v->v+c[i]->v+2*c[i]加上去,本次循环的c[i]也会加上
动态规划的01背包问题,
动态规划的01背包问题,
来自背包九讲上的一段:
-------------------------------------------------------------------------------------------------------
有N件物品和一个容量为V的背包.第i件物品的费用是c[i],价值是w[i].求解将哪些物品装入背包可使价值总和最大.
---------------------------------------------------------------------------------------------------------
基本思路
这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放.
用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值.则其状态转移方程便是:
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的.“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题.如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[i-1][v];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i].
---------------------------------------------------------------------------------------------------------
优化空间复杂度
以上方法的时间和空间复杂度均为O(N*V),其中时间复杂度基本已经不能再优化了,但空间复杂度却可以优化到O(V).
先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组f[i][0..V]的所有值.那么,如果只用一个数组f[0..V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢?f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来,能否保证在推f[i][v]时(也即在第i次主循环中推f[v]时)能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值.伪代码如下:
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]},因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]].
----------------------------------------------------------------------------------------------------------
基本思路我都明白,但是优化空间复杂度由O(N*V)变成O(V)的时候我不明白,为什么v要从V下降到0?现在的f[v]和原来的f[i][v]是什么关系?谁能解释下优化后的伪代码?
来自背包九讲上的一段:
-------------------------------------------------------------------------------------------------------
有N件物品和一个容量为V的背包.第i件物品的费用是c[i],价值是w[i].求解将哪些物品装入背包可使价值总和最大.
---------------------------------------------------------------------------------------------------------
基本思路
这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放.
用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值.则其状态转移方程便是:
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的.“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题.如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[i-1][v];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i].
---------------------------------------------------------------------------------------------------------
优化空间复杂度
以上方法的时间和空间复杂度均为O(N*V),其中时间复杂度基本已经不能再优化了,但空间复杂度却可以优化到O(V).
先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组f[i][0..V]的所有值.那么,如果只用一个数组f[0..V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢?f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来,能否保证在推f[i][v]时(也即在第i次主循环中推f[v]时)能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值.伪代码如下:
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]},因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]].
----------------------------------------------------------------------------------------------------------
基本思路我都明白,但是优化空间复杂度由O(N*V)变成O(V)的时候我不明白,为什么v要从V下降到0?现在的f[v]和原来的f[i][v]是什么关系?谁能解释下优化后的伪代码?
数学人气:741 ℃时间:2020-04-14 16:04:13
优质解答
我来回答
类似推荐
猜你喜欢
- 1已知点A(2,8),B(x1,y1),C(x2,y2)在抛物线y2=2px,(p>0)上,△ABC的重心与此抛物线的焦点F重合(如图) (1)写出该抛物线的方程和焦点F的坐标; (2)求线段BC中点M的坐标; (
- 2一个木材仓库中有一堆木材呈梯形堆放,下层放了19根,上层堆放了9根,一共堆放了11层,这堆木材有多少
- 3who that has such a house does not love it?
- 4一个圆锥形的小麦堆,底面直径为4米,小麦共重4.71吨,如果每立方米小麦重750千克,问这个小麦堆的高为多少米?
- 5在中间加上一个字,使它与上下左右各组成一个新字.
- 6求解方程12.5x+5*(7-x)=50
- 7李师傅计划生产450个零件,工作8小时后还剩330个零件,照这样的速度,共要几时能完成(用方程)记住用方程
- 8求高一英语作文why should we do exercise?
- 9写一篇雨中情的作文
- 10,把3米长的铁丝平均分成7段,每段长是3米的(—— ),每段长( )米