背包问题C++ 动态规划
时间: 2023-07-07 13:12:40 浏览: 79
好的,背包问题是一个经典的动态规划问题,解决的是给定一些物品和一个背包,如何选择物品放入背包使得背包总重量最大。下面是 C++ 的实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
int knapsack(int W, vector<int> wt, vector<int> val, int n) {
vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= W; j++) {
if(wt[i-1] <= j) {
dp[i][j] = max(dp[i-1][j], val[i-1] + dp[i-1][j-wt[i-1]]);
}
else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n][W];
}
int main() {
int W = 50;
vector<int> wt = {10, 20, 30};
vector<int> val = {60, 100, 120};
int n = wt.size();
cout << knapsack(W, wt, val, n) << endl;
return 0;
}
```
其中,`W` 是背包的容量,`wt` 是每个物品的重量,`val` 是每个物品的价值,`n` 是物品的个数。函数 `knapsack` 返回的是在背包容量为 `W` 的情况下,能够装入的最大价值。
这里采用一个二维数组 `dp` 来记录状态。其中 `dp[i][j]` 表示在前 `i` 个物品中,背包容量为 `j` 的情况下,能够装入的最大价值。状态转移方程为:
- 如果当前物品的重量小于等于背包容量,则可以选择装入或不装入,取最大值:
`dp[i][j] = max(dp[i-1][j], val[i-1] + dp[i-1][j-wt[i-1]]);`
- 如果当前物品的重量大于背包容量,则不能装入,直接继承上一个状态:
`dp[i][j] = dp[i-1][j];`
最终返回 `dp[n][W]` 即可。
阅读全文