问题描述
有种ｎ种物品，每种只有一个，第ｉ种物体的体积为w[i],价值为v[i].选一些物品装到一个容量为Ｃ的背包，使得背包内物体体积不超过Ｃ的前提下价值尽量大．
分析
首先约定Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积；定义dp(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值
递推过程：
- 若物品不能装下，则此时的价值与上一个阶段相同，即dp[i][j] = dp[i-1][j];
- 若物品能够装下，但是装下不一定最优，则此时的价值应与i-1作比较，即dp[i][j] =max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
模板题 [http://acm.hdu.edu.cn/showproblem.php?pid=2602]
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll v[1005], w[1005];
ll dp[1005][1005]; // dp[i][j]表示当前背包容量 j，前 i 个物品最佳组合对应的价值
int main() {
ll n, c, t;
cin >> t;
while (t--) {
cin >> n >> c;
for(ll i = 1; i <= n; i++) scanf("%lld", v+i);
for(ll i = 1; i <= n; i++) scanf("%lld", w+i);
memset(dp, 0, sizeof dp);
for(ll i = 1; i <= n; i++) { // 从第一个物体到第n个物体
for(ll j = 0; j <= c; j++) { // 背包容量
if(j >= w[i]) { // 背包能放得开
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
// 前者大就是不放第ｉ个东西价值大，后者就是放第ｉ个东西价值大
}
else// 放不开则等于上一阶段的价值
dp[i][j] = dp[i-1][j];
}
}
cout << dp[n][c] << endl;
}
return 0;
}
拓展
- 输出路径：
放入背包的输出１，否则输出０
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll v[1005], w[1005];
ll dp[1005][1005], path[1005][1005];
int main() {
ll n, c, t;
cin >> t;
while (t--) {
cin >> n >> c;
for(ll i = 1; i <= n; i++) scanf("%lld", v+i);
for(ll i = 1; i <= n; i++) scanf("%lld", w+i);
memset(dp, 0, sizeof dp);
for(ll i = 1; i <= n; i++) {
for(ll j = 0; j <= c; j++) {
if(j >= w[i]) {
if(dp[i-1][j] < dp[i-1][j-w[i]]+v[i]) {
dp[i][j] = dp[i-1][j-w[i]]+v[i];
path[i][j] = 1;
}
else dp[i][j] = dp[i-1][j];
} // 可以放东西
else
dp[i][j] = dp[i-1][j];
}
}
cout << dp[n][c] << endl;
}
for (ll i = 1,j = c;i <= n&&j > 0;i++){
if (path[i][j]) {
printf("1 ");
j -= w[i];
} else printf("0 ");
}
return 0;
}
-
一维数组优化：
用dp[j]表示第i次循环后，前i个物体放到容量j时的最大价值，但是和二维数组不同，第i次循环会可能覆盖第i-1次循环的结果．而且，背包容量j必须逆序枚举．
逆序枚举容量的原因：
注意一点，我们是由第 i - 1 次循环的两个状态推出 第 i 个状态的，而且 ｗ > w- v[i]，则对于第i次循环，背包容量只有当c..0循环时，才会先处理背包容量为v的状况，后处理背包容量为 w-v[i] 的情况。具体来说，由于，在执行v时，还没执行到w- v[i]的, 因此，dp[j - w[i]]保存的还是第i - 1次循环的结果。即在执行第i次循环 且 背包容 量为v时，此时的dp[j]存储的是 dp[j - 1][j] ，此时dp[j-w[i]]存储的 是dp[i - 1][j-w[i]]。
相反，如果在执行第 i 次循环时，背包容量按照0..c的顺序遍历一 遍，来检测第 i 件物品是否能放。此时在执行第i次循环 且 背包容量为v时，此时的dp[j]存储的是 dp[i - 1][v] ，但是，此时dp[j-w[i]]存储的是dp[i][j-w[i]]。
因为，ｗ > w- v[i]，第i次循环中，执行背包容量为j时，容量为ｗ > w- v[i]的背包已经计算过，即dp[j-w[i]]中存储的是dp[j-w[i]]。即，对于01背包，按照增序枚举背包容量是不对的。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll v[1005], w[1005];
ll dp[1005]; // 表示第i次循环后，前i个物体放到容量j时的最大价值
int main() {
ll n, c, t;
cin >> t;
while (t--) {
cin >> n >> c;
for(ll i = 1; i <= n; i++) scanf("%lld", v+i);
for(ll i = 1; i <= n; i++) scanf("%lld", w+i);
memset(dp, 0, sizeof dp);
for(ll i = 1; i <= n; i++) { // 从第一个物体到第n个物体
for(ll j = c; j >= 0; j--) { // 注意此时背包容量要逆序枚举
if(j >= w[i]) { // 背包能放得开
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
// 前者大就是不放第ｉ个东西价值大，后者就是放第ｉ个东西价值大
}
// 第i次循环开始时dp[j]里存储的是第i-1次循环的结果
}
}
cout << dp[c] << endl;
}
return 0;
}
参考博文 https://blog.csdn.net/qq_37767455/article/details/99086678
https://blog.csdn.net/tomorrowtodie/article/details/51090715
https://blog.csdn.net/liusuangeng/article/details/38374405