动态规划法求0-1背包问题请用C++语言编程,代码中请加注释。
时间: 2024-02-18 20:01:53 浏览: 70
好的,下面是C++语言的动态规划法求解0-1背包问题的代码,已经加上了注释:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N, W;
cin >> N >> W; // N为物品的数量,W为背包的容量
vector<int> weight(N+1); // weight[i]表示第i个物品的重量
vector<int> value(N+1); // value[i]表示第i个物品的价值
for(int i = 1; i <= N; i++) {
cin >> weight[i] >> value[i];
}
vector<vector<int>> dp(N+1, vector<int>(W+1)); // dp[i][j]表示前i个物品放入容量为j的背包中能获得的最大价值
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= W; j++) {
if(weight[i] > j) { // 装不下第i个物品
dp[i][j] = dp[i-1][j];
} else { // 能装下第i个物品
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
}
}
}
cout << dp[N][W] << endl; // 输出最大价值
return 0;
}
```
这个代码使用了vector来存储数据,可以根据需要修改。
阅读全文