背包问题泛指以下这一种问题:
给定一组有固定价值和固定重量的物品, 以及一个已知最大承重量的背包, 求在不超过背包最大承重量的前提下, 能放进背包里面的物品的最大总价值.
这一类问题是典型的使用动态规划解决的问题, 我们可以把背包问题分成 3 种不同的子问题: 0-1 背包问题, 完全背包和多重背包问题. 下面对这三种问题分别进行讨论.
一, 0-1 背包
0-1 背包问题是指每一种物品都只有一件, 可以选择放或者不放. 现在假设有 n 件物品, 背包承重为 m.
对于这种问题, 我们可以采用一个二维数组去解决: f[i][j], 其中 i 代表加入背包的是前 i 件物品, j 表示背包的承重, f[i][j] 表示当前状态下能放进背包里面的物品的最大总价值. 那么, f[n][m] 就是我们的最终结果了.
采用动态规划, 必须要知道初始状态和状态转移方程. 初始状态很容易就能知道, 那么状态转移方程如何求呢? 对于一件物品, 我们有放进或者不放进背包两种选择:
(1) 假如我们放进背包, f[i][j] = f[i - 1][j - weight[i]] + value[i], 这里的 f[i - 1][j - weight[i]] + value[i] 应该这么理解: 在没放这件物品之前的状态值加上要放进去这件物品的价值. 而对于 f[i - 1][j - weight[i]] 这部分, i - 1 很容易理解, 关键是 j - weight[i] 这里, 我们要明白: 要把这件物品放进背包, 就得在背包里面预留这一部分空间.
(2) 假如我们不放进背包, f[i][j] = f[i - 1][j], 这个很容易理解.
因此, 我们的状态转移方程就是: f[i][j] = max(f[i][j] = f[i - 1][j] , f[i - 1][j - weight[i]] + value[i])
当然, 还有一种特殊的情况, 就是背包放不下当前这一件物品, 这种情况下 f[i][j] = f[i - 1][j]. 这种场景可以用来初如化 f[i][j].
下面是实现的代码:
- #include <iostream>
- #include <iostream>
- using namespace std;
- #define V 500
- #define N 20
- int weight[N + 1];
- int value[N + 1];
- int f[N + 1][V + 1];
- int main()
- {
- int n, m;
- cout <<"请输入物品个数:";
- cin>> n;
- cout <<"请分别输入" << n << "个物品的重量和价值:" << endl;
- for (int i = 1; i <= n; i++)
- {
- cin>> weight[i]>> value[i];
- }
- cout <<"请输入背包容量:";
- cin>> m;
- for (int i = 1; i <= n; i++)
- {
- for (int j = 1; j <= m; j++)
- {
- if (weight[i]> j)
- {
- f[i][j] = f[i - 1][j]; // 初始化, 假定背包放不下当前这一件物品
- }
- else
- {
- f[i][j] = max(f[i - 1][j], f[i - 1][j - weight[i]] + value[i]);
- }
- }
- }
- cout <<"背包能放的最大价值为:" << f[n][m] << endl;
- return 0;
- }
应用例子: 采药
山洞里有三株不同的草药, 采第一株需要 71 分钟, 采第二株需要 69 分钟, 采第三株需要 1 分钟. 第一株的价值为 100, 第二株的价值为 1, 第三侏的价值为 2. 给你 70 分钟的时间, 你可以让采到的草药的最大的总价值是多少?
分析:
这就是一个 0-1 背包问题, 总时间 70 分钟相当于背包的承重能力, 采每株草药的时间相当于每个物品的重量.
直接运行上面的程序, 可得到结果:
请输入物品个数: 3
请分别输入 3 个物品的重量和价值:
71 100
69 1
1 2
请输入背包容量: 70
背包能放的最大价值为: 3
代码分析:
用 i 表示当前采了几种草药, j 表示用了多少时间
(1) 采第一种草药 i = 1, 所需时间 weight[1] = 71, 价值 value[1] = 100
j = 1 时, f[1][1] = f[0][1] = 0
j = 2 时, f[1][2] = f[0][2] = 0
j = 3 时, f[1][3] = f[0][3] = 0
......
j = 70 时, f[1][70] = f[0][70] = 0
(2) 前两种草药 i = 2,weight[2] = 69,value[2] = 1
j = 1 时, f[2][1] = f[1][1] = 0
j = 2 时, f[2][2] = f[1][2] = 0
j = 3 时, f[2][3] = f[1][3] = 0
......
j = 68 时, f[2][68] = f[1][68] = 0
j = 69 时, j>= weight[i], f[2][69] = max(f[1][69], f[1][0] + value[2]) = max(0, 0 + 1) = 1.max 函数中的第一个参数 f[1][69] 表示采第一株草药用掉全部 69 单位的时间能获取到的价值, 因为第一株草药需要 100 单位的时间, 所以 f[1][69] 得到的价值为 0; 第二个参数 f[1][0] + value[2] 表示采第一株草药用了 0 单位时间, 价值为 0, 把剩余的 69 的时间全用在采第二株草药上, 得到的价值为 1.
j = 70 时, j>= weight[i], f[2][70] = max(f[1][70], f[1][1] + value[2] = max(0, 0 + 1) = 1.max 函数中的第一个参数 f[1][70] 表示采第一株草药用掉全部 70 单位的时间能获取到的价值, 因为第一株草药需要 100 单位的时间, 所以 f[1][70] 得到的价值为 0; 第二个参数 f[1][1] + value[2] 表示采第一株草药用了 1 单位时间, 因为采第一草药需要 100 单位的时间, 所以 1 单位时间不够采第一株草药, 得到的价值为 0, 把剩余的 69 的时间全用在采第二株草药上, 得到的价值为 1.
(3) 前三种草药 i = 3,weight[3] = 1,value[3] = 2
j = 1 时, j>= weight[i], f[3][1] = max(f[2][1], f[2][0] + value[3]) = max(0, 0 + 2) = 2,max 中的第一个参数表示把这 1 秒的时间用来采前两株草药, 第二个参数表示用前 0 秒的时间采前两株草药, 用剩余 1 秒的时间采第三株草药.
j = 2 时, j>= weight[i], f[3][2] = max(f[2][2], f[2][1] + value[3]) = max(0, 0 + 2) = 2
j = 3 时, j>= weight[i], f[3][3] = max(f[2][3], f[2][2] + value[3]) = max(0, 0 + 2) = 2
......
j = 68 时, j>= weight[i], f[3][68] = max(f[2][68], f[2][67] + value[3]) = max(0, 0 + 2) = 2
j = 69 时, j>= weight[i], f[3][69] = max(f[2][69], f[2][68] + value[3]) = max(1, 0 + 2) = 2.max 函数的第一个参数 f[2][69] 表示把 69 单位的时间用在采前两株草药, 事实上只能采到第二株草药, 价值为 1. 第二个参数中的 f[2][68] 表示前 68 单位的时间用来采前两株草药, 无法采到草药, 价值为 0;value[3] 表示把最后一秒的时间用来采第三株草药, 得到的价值为 2.
j = 70 时, f[3][70] = f[2][70] = 0, 此时 j>= weight[i], f[3][70] = max(f[2][70], f[2][69] + value[3]) = max(1, 1 + 2) = 2 =3.max 函数的第一个参数 f[2][70] 表示把 70 单位的时间用在采前两株草药, 事实上只能采到第二株草药, 价值为 1. 第二个参数中的 f[2][69] 表示前 69 单位的时间用来采前两株草药, 可以采到第二株草药, 价值为 1;value[3] 表示把最后一秒的时间用来采第三株草药, 得到的价值为 2, 二者加起来即总价值为 3.
0-1 背包问题还有一种更加节省空间的方法, 那就是采用一维数组去解决, 下面是代码:
- #include <iostream>
- #include <algorithm>
- using namespace std;
- #define V 500
- int weight[20 + 1];
- int value[20 + 1];
- int f[V + 1];
- int main()
- {
- int n, m;
- cout <<"请输入物品个数:";
- cin>> n;
- cout <<"请分别输入" << n << "个物品的重量和价值:" << endl;
- for (int i = 1; i <= n; i++)
- {
- cin>> weight[i]>> value[i];
- }
- cout <<"请输入背包容量:";
- cin>> m;
- for (int i = 1; i <= n; i++)
- {
- for (int j = m; j>= 1; j--)
- {
- if (weight[i] <= j)
- {
- f[j] = max(f[j], f[j - weight[i]] + value[i]);
- }
- }
- }
- cout <<"背包能放的最大价值为:" << f[m] << endl;
- return 0;
- }
代码分析:
1 仍以采草药的例子为例, 总时间 m = 70, 草药数量 n = 3.
(1)i = 1, weight[1] = 71
j = 70, weight[1] <= j 为假.
j = 69, weight[1] <= j 为假.
......
j = 2, weight[1] <= j 为假.
j = 1, weight[1] <= j 为假.
(2)i = 2, weight[2] = 69
j = 70, weight[2] <= j 为真, f[70] = max(f[70], f[1] + value[2]) = max(0, 0 + 1) = 1.max 函数中的第一个参数 f[70] 表示 70 分钟的时间用来采第一株草药. 第二个参数 f[1] + value[2] 表示把前 1 分钟的时间用来采第一株草药, 把剩下的 69 分钟时间用来采第二株草药.
j = 69, weight[2] <= j 为真, f[60] = max(f[69], f[0] + value[2]) = max(0, 0 + 1) = 1.f[0] + value[2] 表示把前 0 分钟的时间用来采第一株草药, 把剩下的 69 分钟用来采第二株草药.
j = 68, weight[2] <= j 为假.
......
j = 1, weight[2] <= j 为假.
(3)i = 3, weight[3] = 1
j = 70, weight[3] <= j 为真, f[70] = max(f[70], f[69] + value[3]) = max(1, 1 + 2) = 3.max 函数中的第一个参数 f[70], 根据 i=2 中的 f[70] 可知是表示前 1 分钟的时间用来采第一株草药后 69 分钟的时间用来采第二株草药. 第二个参数 f[69] + value[3] 表示前 69 分钟的时间用来采前两株草药 (具体是前 0 分钟的时间采第一株后 69 分钟的时间采第二株), 最后一秒用来采第三株.
j = 69, weight[3] <= j 为真, f[69] = max(f[69], f[68] + value[3]) = max(1, 0 + 2) = 2.max 函数中的第一个参数 f[69] 表示这 69 分钟的时间用来采前两株草药的最大价值, 根据 i=2 中的 f[69] 可知具体是前 0 分钟的时间用来采第一株草药后 69 分钟的时间用来采第二株草药. 第二个参数 f[68] + value[3] 表示前 68 分钟的时间用来采前两株草药, 最后一秒用来采第三株.
......
j = 2, weight[3] <= j 为真, f[2] = max(f[2], f[1] + value[3]) = max(0, 0 + 2) = 2.max 函数中的第一个参数 f[2] 表示前个分钟的时间用来采前两株草药. 第二个参数 f[1] + value[3] 表示前 1 分钟的时间用来采前两株草药, 最后一秒用来采第三株.
j = 1, weight[3] <= j 为真, f[1] = max(f[1], f[0] + value[3]) = max(0, 0 + 2) = 2.max 函数中的第一个参数 f[1] 表示这一秒的时间用来采前两株草药. 第二个参数 f[0] + value[3] 表示前 0 分钟的时间用来采前两株草药, 最后一秒用来采第三株.
(4) 最后, f[m] = f[70] 即是所求的答案.
2 第二个 for 循环里面, j 为什么要从大到小枚举, 而不是从小到大枚举?
假如 j 是从小到大枚举, 则代码为:
- for (int i = 1; i <= n; i++)
- {
- for (int j = 1; j <= m; j++)
- {
- if (weight[i] <= j)
- {
- f[j] = max(f[j], f[j - weight[i]] + value[i]);
- }
- }
- }
i = 2,j = 69 时, f[69] = max(f[69], f[0] + value[2]) = max(0, 0 + 1) = 1.
i = 2,j = 70 时, f[70] = max(f[70], f[1] + value[2]) = max(0, 0 + 1) = 1.
i = 3,j = 1 时, f[1] = max(f[1], f[0] + value[3]) = max(0, 0 + 2) = 2.max 函数中的第一个参数 f[1] 表示这 1 分钟的时间用来采前两株草药, f[0] + value[3] 表示前 0 分钟的时间用来采前两株草药, 剩余 1 分钟的时间用来采第三株草药.
i = 3,j = 2 时, f[2] = max(f[2], f[1] + value[3]) = max(0, 2 + 2) = 4.ax 函数中的第一个参数 f[1] 表示这 2 分钟的时间用来采前两株草药, f[1] + value[3] 中的 f[1] 根据 i = 3, j = 1 的情景表示前 0 分钟的时间用来采前两株草药, 第 1 分钟的时间用来采第三株草药, value[3] 表示第 2 秒的时间用来采第三株草药. 注意这里第三株草药在第 1 分钟的时间里采了一次, 第 2 分钟又采了一次, 所以出错.
可以把下一段代码
- for (int i = 1; i <= n; i++)
- {
- for (int j = m; j>= 1; j--)
- {
- if (weight[i] <= j)
- {
- f[j] = max(f[j], f[j - weight[i]] + value[i]);
- }
- }
- }
进一步简化为:
- for (int i = 1; i <= n; i++)
- {
- for (int j = m; j>= weight[i]; j--)
- {
- f[j] = max(f[j], f[j - weight[i]] + value[i]);
- }
- }
二, 完全背包
完全背包和 01 背包十分相像, 区别就是完全背包中的每种物品有无限件. 由之前的选或者不选转变成了选或者不选, 选的话要选几件. 下面给出实现代码:
- #include <iostream>
- #include <algorithm>
- using namespace std;
- #define V 500
- int weight[20 + 1];
- int value[20 + 1];
- int f[V + 1];
- int main()
- {
- int n, m;
- cout <<"请输入物品个数:";
- cin>> n;
- cout <<"请分别输入" << n << "个物品的重量和价值:" << endl;
- for (int i = 1; i <= n; i++)
- {
- cin>> weight[i]>> value[i];
- }
- cout <<"请输入背包容量:";
- cin>> m;
- for (int i = 1; i <= n; i++)
- {
- for (int j = weight[i]; j <= m; j++)
- {
- f[j] = max(f[j], f[j - weight[i]] + value[i]);
- }
- }
- cout <<"背包能放的最大价值为:" << f[m] << endl;
- return 0;
- }
仍以上面的采草药为例, 运行结果为:
请输入物品个数: 3
请分别输入 3 个物品的重量和价值:
71 100
69 1
1 2
请输入背包容量: 70
背包能放的最大价值为: 140
分析:
1 完全背包的代码与 0-1 背包的代码只有一行区别. 完全背包中的 j 是从小到大按顺序枚举的, 而 0-1 背包中的 j 是从大到小逆序枚举的.
2 程序执行过程
(1)i = 1 时, j = weight[i] = 71, j <= m 为假, 循环不执行.
(2)i = 2 时, weight[2] = 69,value[2] = 1
j = 69, f[69] = max(f[69], f[0] + value[2]) = max(0, 0 + 1) = 1.max 中的第一个参数 f[69] 表示把 69 分钟的时间用于第一株草药, 价值是 0. 第二个参数中的 f[0] 表示前 0 分钟采到到草药的总价值, value[2] 表示剩下的 69 分钟用于采第 2 株草药.
j = 70, f[70] = max(f[70], f[1] + value[2]) = max(0, 0 + 1) = 1.max 中的第一个参数 f[70] 表示把 70 分钟的时间用于第一株草药, 价值是 0. 第二个参数中的 f[1] 表示前 1 分钟采到到草药的总价值, value[2] 表示剩下的 69 分钟用于采第 2 株草药.
(3)i = 3 时, weight[3] = 1, value[3] = 2
j = 1, f[1] = max(f[1], f[0] + value[3]) = max(0, 0 + 2) = 2.max 中的第一个参数 f[1] 表示把 1 分钟的时间用于采前两株草药, 价值是 0. 第二个参数中的 f[0] 表示前 0 分钟采到草药的总价值, value[3] 表示剩下的 1 分钟用于采第 3 株草药.
j = 2, f[2] = max(f[2], f[1] + value[3]) = max(0, 2 + 2) = 4.max 中的第一个参数 f[2] 表示把 2 分钟的时间用于采前两株草药, 价值是 0. 第二个参数中的 f[1] 表示前 1 分钟采到草药的总价值, value[3] 表示剩下的 1 分钟用于采第 3 株草药.
j = 3, f[3] = max(f[3], f[2] + value[3]) = max(0, 4 + 2) = 6.max 中的第一个参数 f[3] 表示把 3 分钟的时间用于采前两株草药, 价值是 0. 第二个参数中的 f[2] 表示前 2 分钟采到草药的总价值, value[3] 表示剩下的 1 分钟用于采第 3 株草药.
......
j = 68, f[68] = max(f[68], f[67] + value[3]) = max(0, 134 + 2) = 136.max 中的第一个参数 f[68] 表示把 68 分钟的时间用于采前两株草药, 价值是 0. 第二个参数中的 f[67] 表示前 67 分钟采到到草药的总价值, value[3] 表示剩下的 1 分钟用于采第 3 株草药.
j = 69, f[69] = max(f[69], f[68] + value[3]) = max(1, 136 + 2) = 138.max 中的第一个参数 f[69] 表示把 69 分钟的时间用于采前两株草药, 价值是 1. 第二个参数中的 f[68] 表示前 68 分钟采到到草药的总价值, value[3] 表示剩下的 1 分钟用于采第 3 株草药.
j = 70, f[70] = max(f[70], f[69] + value[3]) = max(1, 138 + 2) = 140.max 中的第一个参数 f[70] 表示把 70 分钟的时间用于采前两株草药, 价值是 1. 第二个参数中的 f[69] 表示前 69 分钟采到草药的总价值, value[3] 表示剩下的 1 分钟用于采第 3 株草药.
三, 多重背包
多重背包问题限定了一种物品的个数, 解决多重背包问题, 只需要把它转化为 0-1 背包问题即可. 比如, 有 2 件价值为 5, 重量为 2 的同一物品, 我们就可以分为物品 a 和物品 b,a 和 b 的价值都为 5, 重量都为 2, 但我们把它们视作不同的物品.
实现代码:
- #include <iostream>
- #include <algorithm>
- using namespace std;
- #define V 1000
- int weight[50 + 1];
- int value[50 + 1];
- int num[20 + 1];
- int f[V + 1];
- int main()
- {
- int n, m;
- cout <<"请输入物品个数:";
- cin>> n;
- cout <<"请分别输入" << n << "个物品的重量, 价值和数量:" << endl;
- for (int i = 1; i <= n; i++)
- {
- cin>> weight[i]>> value[i]>> num[i];
- }
- int k = n + 1;
- for (int i = 1; i <= n; i++)
- {
- while (num[i] != 1)
- {
- weight[k] = weight[i];
- value[k] = value[i];
- k++;
- num[i]--;
- }
- }
- k--;
- cout <<"请输入背包容量:";
- cin>> m;
- for (int i = 1; i <= k; i++)
- {
- for (int j = m; j>= weight[i]; j--)
- {
- f[j] = max(f[j], f[j - weight[i]] + value[i]);
- }
- }
- cout << "背包能放的最大价值为:" << f[m] << endl;
- return 0;
- }
仍旧以采草药为例, 运行结果:
请输入物品个数: 3
请分别输入 3 个物品的重量, 价值和数量:
- 71 100 2
- 69 1 2
- 1 2 2
请输入背包容量: 70
背包能放的最大价值为: 4
分析:
(1) 第二个 for 的作用是将同样的物品进行拆分.
- weight[4] = weight[1]; value[4] = value[1];
- weight[5] = weight[2]; value[5] = value[2];
- weight[6] = weight[3]; value[6] = value[3];
(2) 最终拆分后的物品总数量 k = 6.
少儿编程咨询, 算法咨询请加微信 307591841 或 QQ 群 581357582
信息学竞赛公众号. jpg
来源: http://www.jianshu.com/p/8fb126d49abf