Cpp 写一个背包问题
时间: 2023-07-07 15:34:54 浏览: 38
好的,下面是一个使用动态规划求解 01 背包问题的 C++ 代码:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1005;
int w[MAXN], v[MAXN]; // w[i] 表示第 i 个物品的重量,v[i] 表示第 i 个物品的价值
int dp[MAXN]; // dp[i] 表示背包容量为 i 时,能够获得的最大价值
int main()
{
int n, m; // n 表示物品个数,m 表示背包容量
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i];
}
memset(dp, 0, sizeof(dp)); // 初始化 dp 数组
for (int i = 1; i <= n; i++) { // 枚举每一个物品
for (int j = m; j >= w[i]; j--) { // 枚举背包容量
dp[j] = max(dp[j], dp[j - w[i]] + v[i]); // 状态转移方程
}
}
cout << dp[m] << endl; // 输出背包容量为 m 时,能够获得的最大价值
return 0;
}
```
这段代码中,我们使用了一个一维数组 `dp` 来表示背包的状态。状态转移方程为 `dp[j] = max(dp[j], dp[j - w[i]] + v[i])`,表示当背包容量为 `j` 时,能够获得的最大价值为当前状态 `dp[j]` 和加入第 `i` 个物品后的状态 `dp[j - w[i]] + v[i]` 中的较大值。