货郎担问题动态规划算法c++代码
时间: 2023-08-07 20:43:15 浏览: 193
以下是货郎担问题的动态规划算法的C++代码实现:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int knapsack(vector<int>& weight, vector<int>& value, int capacity) {
int n = weight.size(); // 物品数量
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1)); // 初始化动态规划数组
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= capacity; ++j) {
if (weight[i - 1] <= j) {
// 当前物品可以放进背包
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
} else {
// 当前物品无法放进背包
dp[i][j] = dp[i - 1][j];
}
}
}
// 返回最大价值
return dp[n][capacity];
}
int main() {
vector<int> weight = {2, 2, 6, 5, 4};
vector<int> value = {6, 3, 5, 4, 6};
int capacity = 10;
int max_value = knapsack(weight, value, capacity);
cout << "The maximum value is: " << max_value << endl;
return 0;
}
```
其中,`weight` 表示每个物品的重量,`value` 表示每个物品的价值,`capacity` 表示背包的容量。函数返回背包能够装下的最大价值。
阅读全文