货郎担问题动态规划算法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` 表示背包的容量。函数返回背包能够装下的最大价值。