动态规划背包问题 C++代码

下面是一个简单的 01 背包问题的动态规划实现，用 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 w = 1; w <= W; w++) {
            if (wt[i-1] <= w) {
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);
            }
            else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }

    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;
}

以上代码中，`knapsack` 函数实现了 01 背包问题的动态规划解法，接受背包的容量 `W`、物品重量 `wt`、物品价值 `val` 和物品数量 `n` 作为输入，返回能够装入背包的最大价值。

具体来说，我们可以使用一个二维数组 `dp` 来存储解决子问题的结果。`dp[i][w]` 表示前 `i` 个物品，容量为 `w` 的背包最多能装多少价值的物品。

状态转移方程为：

dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])

其中，`i` 表示当前考虑到的物品编号，`w` 表示当前背包的容量。如果当前物品的重量小于等于当前背包的容量，我们可以选择将当前物品放入背包，也可以选择不放入。如果选择放入，则背包的剩余容量为 `w-wt[i-1]`，此时可以装入的最大价值为 `val[i-1] + dp[i-1][w-wt[i-1]]`；如果选择不放入，则背包的容量不变，此时可以装入的最大价值为 `dp[i-1][w]`。我们在两种情况中取较大值即可。