Python 0/1背包、动态规划
【摘要】 参考：http://www.cnblogs.com/fcyworld/p/6243012.html
Python 0/1背包、动态规划
0/1背包问题：在能承受一定重量的背包中，放入重量不同，价值不同的几件物品，怎样放能让背包中物品的价值最大？
比如，有三件物品重量w,价值v分别是
w=[5,3,2]
v=[9,7,8]
包的容量是5，也就是...
参考：http://www.cnblogs.com/fcyworld/p/6243012.html
Python 0/1背包、动态规划
0/1背包问题：在能承受一定重量的背包中，放入重量不同，价值不同的几件物品，怎样放能让背包中物品的价值最大？
比如，有三件物品重量w,价值v分别是
w=[5,3,2]
v=[9,7,8]
包的容量是5，也就是我们要求得
maxVal=v1+v2+v3……
约束条件为：ws=w1+w2+w3……
我们的思路是，列举出所有可能的放入背包的选项，然后比较哪个价值大，这需要用到决策树。
决策树的思想是，用一组向量来描述当前的状态，比如 [当前考虑的物品i, 当前背包的空间w， 当前已获得的价值v]，
决策树左儿子表示不选取当前物品np，右儿子表示选取当前
文章来源: blog.csdn.net，作者：网奇，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/jacke121/article/details/78177904
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）