【动态规划笔记】动态规划初始化细节问题:恰好装满背包

求最优解的背包问题中,有的题目要求【恰好装满背包】,有的题目并【没有要求】必须把背包装满
实现方法:
初始化有所不同
设:F[i]表示容量为i的背包能够装的最大价值
恰好装满背包:
初始化:    F[0]=0,F[i]=-INF, 1<=i<=V 不用恰好装满背包: 初始化:    F[i]=0,0<=i<=V ?理解: 初始化的F数组事实上就是在没有任何物品可以放入背包时的合法状态。 如果要求背包恰好装满: (1)容量为0 的背包不放入任何物品,恰好装满 ,价值为0,所以初始化为0 (2)容量不为0的背包不放入任何物品,不能恰好装满,所以初始化为-INF,如果求最小值,初始化为INF 循环后判断F[V]是否等于INF,来判断能否选出若干个物品使背包恰好装满? 如果不要求背包恰好装满: F数组全部初始化为0,因为不放入任何物品,所得的价值就是0

【动态规划笔记】动态规划初始化细节问题:恰好装满背包最先出现在Python成神之路

版权声明:
作者:lichengxin
链接:https://www.techfm.club/p/16424.html
来源:TechFM
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>