C++实现 【问题描述】使用动态规划算法解0-1背包问题,具体来说就是,依据递归式,按照顺序求得子问题,使得选择合适物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。 【输入形式】在屏幕上输入背包容量、物品数量、每件物品价值和重量。 【输出形式】最优解时所选物品的价值总和及其编号。
时间: 2023-07-20 16:11:17 浏览: 205
好的,以下是C++代码实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int C, n; // 背包容量,物品数量
cin >> C >> n;
vector<int> w(n+1), v(n+1); // 物品重量和价值
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
vector<vector<int>> f(n+1, vector<int>(C+1)); // f[i][j]表示前i个物品放入容量为j的背包中可获得的最大价值
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= C; j++) {
if (j < w[i]) {
f[i][j] = f[i-1][j];
} else {
f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i]);
}
}
}
int res = f[n][C]; // 最大价值
cout << "最大价值:" << res << endl;
vector<int> selected; // 所选物品的编号
int j = C;
for (int i = n; i >= 1; i--) {
if (f[i][j] > f[i-1][j]) {
selected.push_back(i);
j -= w[i];
}
}
cout << "所选物品编号:";
for (int i = selected.size()-1; i >= 0; i--) {
cout << selected[i] << " ";
}
cout << endl;
return 0;
}
```
希望能对你有所帮助!
阅读全文