广告
淘宝内部优惠券
当前位置: 开发异常方案库» C/C++ » 如何理解01背包的状态转移方程?

如何理解01背包的状态转移方程?

开发异常方案库  收集整理于:2020-05-27 22:07:00  浏览:66次
感觉对这一段代码不是很理解
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
“f[i-1][v]代表的就是不将这件物品放入背包,而f[i-1][v-c[i]]+w[i]则是代表将第i件放入背包之后的总价值,比较两者的价值,得出最大的价值存入现在的背包之中。” 可是,一个物体放入背包肯定比不放入时的价值大啊,这有什么比较的必要吗?

------网友观点--------------------
有一个判断条件你没写,这个是容量作为下标,你得考虑背包是否放满

------网友观点--------------------
单看这个肯定没必要呀

------网友观点--------------------
f[i-1][v-c[I]] +.  w[I] 去掉一个    换上另一个

------网友观点--------------------
引用 楼主 Jennie Libra 的回复:
感觉对这一段代码不是很理解
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
“f[i-1][v]代表的就是不将这件物品放入背包,而f[i-1][v-c[i]]+w[i]则是代表将第i件放入背包之后的总价值,比较两者的价值,得出最大的价值存入现在的背包之中。” 可是,一个物体放入背包肯定比不放入时的价值大啊,这有什么比较的必要吗?
不放入该背包就不消耗容量,可能放后续背包后总的价值更大

------网友观点--------------------
有max函数的产生 前提是后面f[i-1][v-c[i]]+w[i]产生 而这个式子的产生的前提是第i个物品放入不会超过背包的容量 
发布此文章仅为传递网友分享,不代表本站观点,若侵权请联系我们删除,本站将不对此承担任何责任。
软件开发 程序错误 异常 ybaby.netCopyright © 2020-2026  ybaby 版权所有  桂ICP备17004385号-2 网站地图