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 |
用简单的一维数组来写，方便大家理解
看代码吧！！！
版权声明：本文为hdushsh原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。