用c++写01背包问题

以下是使用 C++ 编写的 01 背包问题代码：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, w;
    cin >> n >> w;

    vector<int> weight(n + 1);
    vector<int> value(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }

    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 (j >= weight[i]) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    cout << dp[n][w] << endl;

    return 0;
}

这里使用动态规划来解决 01 背包问题，其中 `n` 表示物品个数，`w` 表示背包容量。`weight` 和 `value` 分别表示每个物品的重量和价值。`dp` 是一个二维数组，`dp[i][j]` 表示前 `i` 个物品放入容量为 `j` 的背包中所能获得的最大价值。

具体的求解过程是，对于每个物品 `i`，都有两种选择：放入背包或不放入背包。如果选择放入背包，则当前背包容量需要减去物品 `i` 的重量，即 `j - weight[i]`，此时的最大价值为 `dp[i-1][j-weight[i]] + value[i]`；如果选择不放入背包，则当前的最大价值为 `dp[i-1][j]`。因此，可以使用以下公式来进行状态转移：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])      (j >= weight[i])
dp[i][j] = dp[i-1][j]                                           (j < weight[i])

最终的答案即为 `dp[n][w]`。