【动态规划笔记】动态规划初始化细节问题:恰好装满背包
求最优解的背包问题中,有的题目要求【恰好装满背包】,有的题目并【没有要求】必须把背包装满
实现方法:
初始化有所不同
设: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
版权声明:
作者:lichengxin
链接:https://www.techfm.club/p/16424.html
来源:TechFM
文章版权归作者所有,未经允许请勿转载。
THE END
二维码
共有 0 条评论