dp动态规划中的背包问题01
来源:学生作业帮 编辑:搜狗做题网作业帮 分类:数学作业 时间:2024/05/17 06:31:34
dp动态规划中的背包问题01
背包问题有几步处理并不太明白,
(1)
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
转化为
f[v]=max{f[v],f[v-c[i]]+w[i]} 时,为什么0...v的顺序要变成逆顺序 v...0
(2)
注意f[i][v]有意义当且仅当存在一个前i件物品的子集,其费用总和为v.所以按照这个方程递推完毕后,最终的答案并不一定是f[N] [V],而是f[N][0..V]的最大值.如果将状态的定义中的“恰”字去掉,在转移方程中就要再加入一项f[i][v-1],这样就可以保证f[N] [V]就是最后的答案.至于为什么这样就可以,由你自己来体会了.
还有希望可以解答上面这段话的含义.
背包问题有几步处理并不太明白,
(1)
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
转化为
f[v]=max{f[v],f[v-c[i]]+w[i]} 时,为什么0...v的顺序要变成逆顺序 v...0
(2)
注意f[i][v]有意义当且仅当存在一个前i件物品的子集,其费用总和为v.所以按照这个方程递推完毕后,最终的答案并不一定是f[N] [V],而是f[N][0..V]的最大值.如果将状态的定义中的“恰”字去掉,在转移方程中就要再加入一项f[i][v-1],这样就可以保证f[N] [V]就是最后的答案.至于为什么这样就可以,由你自己来体会了.
还有希望可以解答上面这段话的含义.
(1)
将二维数组转化为一维数组之后,f[v]表示v的容量最多装多大价值.
如果顺序枚举的话,每种物品可能多次使用.例如某个物品重量为5,价值为10,那么就会用f[0]去更新f[5],用f[5]去更新f[10],最后出现f[0]=0,f[5]=10,f[10]=20的情况.而这是01背包,要求每种物品只能用一次.
逆序枚举时,是在f[5]被f[0]更新之前,就用f[5]更新f[10],这样就可以保证用一次.
(2)
首先要搞明白f[i][v]的定义:用前i种物品恰好装满一个容量为v的背包,最大价值是多少.
这句话的意思就是说,费用总和为v的状态可能没有意义.譬如说所有物品加在一起的重量都不到v,那么f[N][V]必然没有意义了.只能去找f[N][0..V]中的最大值来输出.
但是如果我们改变一下f[i][v]的定义:用前i种物品,在总重不超过v的情况下,最大价值是多少.
就可以直接输出f[N][V]了,这样只需要改变一下转移方程,加上一项f[i][v-1].
还有问题请追问.
再问: 我明白了,谢谢你的回答啊,找了很多解释,还是你的最清楚了
将二维数组转化为一维数组之后,f[v]表示v的容量最多装多大价值.
如果顺序枚举的话,每种物品可能多次使用.例如某个物品重量为5,价值为10,那么就会用f[0]去更新f[5],用f[5]去更新f[10],最后出现f[0]=0,f[5]=10,f[10]=20的情况.而这是01背包,要求每种物品只能用一次.
逆序枚举时,是在f[5]被f[0]更新之前,就用f[5]更新f[10],这样就可以保证用一次.
(2)
首先要搞明白f[i][v]的定义:用前i种物品恰好装满一个容量为v的背包,最大价值是多少.
这句话的意思就是说,费用总和为v的状态可能没有意义.譬如说所有物品加在一起的重量都不到v,那么f[N][V]必然没有意义了.只能去找f[N][0..V]中的最大值来输出.
但是如果我们改变一下f[i][v]的定义:用前i种物品,在总重不超过v的情况下,最大价值是多少.
就可以直接输出f[N][V]了,这样只需要改变一下转移方程,加上一项f[i][v-1].
还有问题请追问.
再问: 我明白了,谢谢你的回答啊,找了很多解释,还是你的最清楚了
动态规划的0-1背包问题,请高手解释下代码
求动态规划0/1背包问题的经典习题及测试数据
0-1背包问题的多种解法代码(动态规划、贪心法、回溯法、分支限界法)
背包问题的算法登上算法、递归算法、贪婪算法、动态规划算法利用matlab编程实现我把我仅有的分都给了
ACM动态规划问题刘汝佳的算法白皮书上DP三角形求最大和那道题,书上有3中方法,第一种是递归计算,第二种递推计算,第三种
ACM DP动态规划题 :通过加入字符,使一字符串对称,求加入字符的最小个数.
动态规划算法
分别用贪心算法和动态规算法求解0/1背包问题的最优解和最大收益
西北工业大学运筹学真题 :1.试述建立动态规划数学模型的步骤及应注意的问题,并说明动态规划的求解方法有
用动态规划,分治法,回溯发,分枝限界法解下列0-1背包为题例题:n=3,w=[100,14,10],p=[20,18,1
贪心算法 部分背包问题
c语言 数字三角形的动态规划