Java实现01背包问题的思路
0-1背包问题:
给定N件物品和一个容量为V的背包。放入第i件物品耗费的空间为weight[i] ,得到的价值是 value[i] 。
问:哪些物品装入背包可使价值总和最大?最大是多少?
解题思路:
假设背包容量为8,有五间物品分别如下:
物品 | 重量 | 价值 |
---|---|---|
1 | 6公斤 | 48元 |
2 | 1公斤 | 7元 |
3 | 5公斤 | 40元 |
4 | 2公斤 | 12元 |
5 | 1公斤 | 8元 |
面对每个物品,我们只有选择拿与不拿两种选择,不能够选择装入物品的一部分,也不能装入同一物品多次。
重量 | 价值 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
6 | 48 | 0 | 0 | 0 | 0 | 0 | 48 | 48 | 48 |
1 | 7 | 7 | 7 | 7 | 7 | 7 | 48 | 55 | 55 |
5 | 40 | 7 | 7 | 7 | 7 | 40 | 48 | 55 | 55 |
2 | 12 | 7 | 12 | 19 | 19 | 40 | 48 | 55 | 60 |
1 | 8 | 8 | 15 | 20 | 27 | 40 | 48 | 56 | 63 |
用简单的一维数组来写,方便大家理解
看代码吧!!!
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggbcii
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13