动态规划解决0/1背包问题的C++代码,满足如下条件:输入格式: 第1行是M和n,表示背包容量为M且有n件物品; 第2行是这n件物品的重量w i ; 第3行是各物品的价值p i ,背包容量和物品重量都为整数。 输出格式: 第1行是所选物品的价值之和,以及重量之和; 第2行是各物品装入背包的量,即x i 值。
时间: 2024-03-01 21:50:42 浏览: 40
以下是符合要求的C++代码,解决0/1背包问题:
```c++
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 1005;
int M, n;
int w[MAXN], p[MAXN];
int f[MAXN][MAXN], x[MAXN];
int main() {
cin >> M >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i];
}
for (int i = 1; i <= n; i++) {
cin >> p[i];
}
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= M; j++) {
if (j >= w[i]) {
f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + p[i]);
} else {
f[i][j] = f[i - 1][j];
}
}
}
cout << f[n][M] << " ";
int v = M;
for (int i = n; i >= 1; i--) {
if (f[i][v] == f[i - 1][v]) {
x[i] = 0;
} else {
x[i] = 1;
v -= w[i];
}
}
cout << M - v << endl;
for (int i = 1; i <= n; i++) {
cout << x[i] * (M - v) << " ";
}
cout << endl;
return 0;
}
```
该代码使用二维数组f[i][j]表示前i件物品放入容量为j的背包中所能获得的最大价值,其中f[i][j]的值为:
- 若j >= w[i],则f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + p[i]),即第i件物品放入背包中与不放入背包中所能获得的最大价值的较大值;
- 若j < w[i],则f[i][j] = f[i - 1][j],即第i件物品放不下,只能选择不放。
最终输出选取的物品的总价值和总重量以及每个物品装入背包的量。