0-1背包问题、贪⼼算法、动态规划
1、0-1背包问题
0-1背包问题：有⼀个贼在偷窃⼀家商店时，发现有n件物品，第i件物品价值v 元，重w 磅，此处v 与w 都是整数。他希望带⾛的东西越值钱越好，但他的背包中⾄多只能装下W磅的东西，W为⼀整数。应该带⾛哪⼏样东西？这个问题之所以称为0-1背包，是因为每件物品或被带⾛；或被留下；⼩偷不能只带⾛某个物品的⼀部分或带⾛同⼀物品两次。
注：在选择装⼊背包的物品时，对每种物品i只有2种选择，即装⼊背包或不装⼊背包。不能将物品i装⼊背包多次，也不能只装⼊部分的物品i。（⽐如⽟器，花瓶等）
磁力链接怎么用在（分数（部分））背包问题（fractional knapsack problem)中，场景与上⾯问题⼀样，但是窃贼可以带⾛物品的⼀部分，⽽不必做出0-1的⼆分选择。可以把0-1背包问题的⼀件物品想象成⼀个⾦锭，⽽部分问题中的⼀件物品则更像⾦沙。
2、贪⼼算法（按单位重量价值排序）（含为什么不可以解决）
⾸先声明：虽然两个问题相似，但我们可以⽤贪⼼策略可以求解背包问题，⽽不能求解0-1背包问题，为了求解部分数背包问题，我们⾸先计算每个商品的每磅价值v /w 对于这个问题，⼀开始确实有点不
太好⼊⼿。⼀堆的物品，每⼀个都有⼀定的质量和价值，我们能够装⼊的总重量有限制，该怎么来装使得价值最⼤呢？对于这n个物品，每个物品我们可能会选，也可能不选，那么我们总共就可能有2^n种组合选择⽅式。如果我们采⽤这种办法来硬算的话，则整体的时间复杂度就达到指数级别的，肯定不可⾏。
现在我们换⼀种思路。既然每⼀种物品都有价格和重量，我们优先挑选那些单位价格最⾼的是否可⾏呢？⽐如在下图中，我们有3种物品，他们的重量和价格分别是10, 20, 30 kg和60, 100, 120。
那么按照单位价格来算的话，我们最先应该挑选的是价格为60的元素，选择它之后，背包还剩下50 - 10 =40kg。再继续前⾯的选择，我们应该挑选价格为100的元素，这样背包⾥的总价值为60 + 100 = 160。所占⽤的重量为30, 剩下20kg。因为后⾯需要挑选的物品为30kg已经超出背包的容量了。我们按照这种思路能选择到的最多就是前⾯两个物品。如下图：
i i i i i i。遵循贪⼼策略，⼩偷⾸先尽量多地拿⾛每磅价值最⾼的商品，如果该商品已全部拿⾛⽽背包未装满，他继续尽量多地拿⾛每磅价值第⼆⾼的商品，依次类推，直到达到重量上限W。因此，通过将商品按每磅价值排序，贪⼼算法的时间运⾏时间是O(nlgn)。
按照我们前⾯的期望，这样选择得到的价值应该是最⼤的。可是由于有⼀个背包重量的限制，这⾥只⽤了
30kg，还有剩下20kg浪费了。这会是最优的选择吗？我们看看所有的选择情况：
很遗憾，在这⼏种选择情况中，我们前⾯的选择反⽽是带来价值最低的。⽽选择重量分别为20kg和30kg的物品带来了最⼤的价值。看来，我们刚才这种选择最佳单位价格的⽅式也⾏不通。
⽹上基本上证明“贪⼼算法不能解决0-1背包问题“都是采⽤上⾯的例⼦，但是我起初在想可不可以在”按照单位重量价值“排序以后，从每个点都开始⼀次贪⼼遍历呢？⽐如上例，从10 ⾛⼀趟，再从20⾛⼀趟。。。。。。
天真了！主要是被上⾯例⼦迷惑了。。。。。
看这个例⼦：背包可承受100
id ...... 5 6 7 8 9. (20)
v/w 5 6 7 8 9 1000000
W 20 20 20 20 20 80
在上⾯例⼦中，按贪⼼计算的话是选择5,6,7,8,9，，但是明显可以看出应该选5，20。也就是贪⼼算法⽆法从“当前全局”去决策！⽐如从5号开始，遍历到9号，已经背包满了，再往后遍历，即使有最优解也⽆法剔除前⾯已经装进去的。。。
最重要的原因是下⾯这条：
对于0-1背包问题，贪⼼选择之所以不能得到最优解是因为：它⽆法保证最终能将背包装满，部分闲置的背包空间使每公⽄背包空间的价值降低了。
事实上，在考虑0-1背包问题时，应⽐较选择该物品和不选择该物品所导致的最终⽅案，然后再作出最好选择。由此就导出许多互相重叠的⼦问题。这正是该问题可⽤动态规划算法求解的另⼀重要特征。
3、动态规划
f[i][v]：表⽰前i件物品恰放⼊⼀个容量为v的背包可以获得的最⼤价值。
状态转移⽅程是：f[i][v]=max{f[i-1][v],f[i-1][v-weight[i]]+value[i]} //这个⽅程⾮常重要，基本上所有跟背包相关的问题的⽅程都是由它衍⽣出来的。
解释⼀下上⾯的⽅程：“将前i件物品放⼊容量为v的背包中”这个⼦问题，如果只考虑第i件物品放或者不放，那么就可以转化为只涉及前i-1件物品的问题：机遇作文
即1、如果不放第i件物品，则问题转化为“前i-1件物品放⼊容量为v的背包中”；
2、如果放第i件物品，则问题转化为“前i-1件物品放⼊剩下的容量为v-weight[i]的背包中”，此时能获得的最⼤价值就是f [i-1][v-weight[i]]再加上通过放⼊第i件物品获得的价值value[i]。
则f[i][v]的值就是1、2中最⼤的那个值。
[cpp]
1. // 背包问题
2. #include <iostream>
3. #include <algorithm>
4. using namespace std;
5.
6. #define N 3 // N件宝贝
7. #define C 5 // C是背包的总capacity
8.
9. int main()
10. {
11. int value[N + 1] = { 0, 60, 100, 120 }; // 价值
12. int weight[N + 1] = { 0, 1, 2, 3 }; // 重量
13. int f[N + 1][C + 1] = { 0 }; // f[i][j]表⽰在背包容量为j的情况下，前i件宝贝的最⼤价值
14.
15. int i = 1;
16. int j = 1;
17. for (i = 1; i <= N; i++) //外循环控制物品数量，确保每个物品都会被遍历到
18. {
19. /*for (j = weight[i]; j <= C; j++) //内循环控制物品的重量，确保能够遍历出“以前每个物
品放⼊时的最⼤价值f[i][j]”
20. {
21. int x = f[i - 1][j]; //不放第i件物品
22. int y = f[i - 1][j - weight[i]] + value[i]; //放⼊第i件物品
23. f[i][j] = max(x, y);
24. }*/
25.
26. for (j = 1; j <= C; j++)
27. {
28. // 递推关系式
29. if (j < weight[i])
30. {
31. f[i][j] = f[i - 1][j];
32. }
33. else
34. {
35. int x = f[i - 1][j];
36. int y = f[i - 1][j - weight[i]] + value[i];
37. f[i][j] = max(x, y);
38. }
39. }
40. }
3.15活动方案
41.
42. for (i = 0; i <= N; i++)
43. {
44. for (j = 0; j <= C; j++)
45. {
46. printf("%4d ", f[i][j]);
47. }
48.
49. cout << endl;
50. }
51.
52. cout << endl << "选取的最⼤价值是：" << f[N][C] << endl;
53. cout << "选取的物品如下：" << endl;
54. i = N, j = C;
55. while (i)
56. {
57. if (f[i][j] == (f[i - 1][j - weight[i]] + value[i]))
58. {
地狱边境 limbo59. cout << i << ":" << "weight=" << weight[i] << ", value=" << value[i] << endl;
60. j -= weight[i];
61. }
62. i--;
63. }
64.
低值易耗品有哪些65. cout << endl;红岩每章内容概括
66. return 0;
67. }
运⾏结果：
如果把上⾯代码中内循环改成注释部分，则运⾏结果如下：（个⼈认为写成注释部分的代码，更容易理解）
以上⽅法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。
结合上⾯的例⼦，有三件物品，背包的最⼤负重量是5，求可以取得的最⼤价值。为了⽅⾯说明，物品weight 依次为：1，2，3。⼆维数组下的求解顺序，物品数1--->n, 背包容量1--->w。如图，要使⽤⼀维数组，背包容量要采⽤倒序，即w--->1, 只有这样对于⽅程 dp( j ) = Max( dp( j ), dp (j-w[i] ) + v[i] )，才能达到等式左边才表⽰i，⽽等式右边表⽰i-1的效果。
优化空间复杂度：
上⾯f[i][v]使⽤⼆维数组存储的，可以优化为⼀维数组f[v]，将主循环改为：
for i = 1..N；
for v = V..0；
f[v] = max（f[v]， f[v-c[i]]+w[i]）；
即将第⼆层循环改为从V..0，逆序。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论