用c++写01背包问题

以下是使用动态规划思想，用C++实现01背包问题的代码：

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    int n, W;
    cin >> n >> W; // n表示物品数量，W表示背包容量

    int w[n+1], v[n+1];
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i]; // 输入每个物品的重量和价值
    }

    int dp[n+1][W+1];
    memset(dp, 0, sizeof(dp)); // 初始化dp数组

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (j >= w[i]) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]); // 状态转移方程
            }
            else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    cout << dp[n][W] << endl; // 输出最大价值
    return 0;
}

输入样例：

4 5
2 3
1 2
3 4
2 2

输出样例：

7

其中，dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

其中，dp[i-1][j]表示不选择第i个物品时的最大价值，dp[i-1][j-w[i]] + v[i]表示选择第i个物品时的最大价值。如果背包容量j小于当前物品重量w[i]，则无法放入背包中，此时dp[i][j]等于dp[i-1][j]。最终输出dp[n][W]即为所求的最大价值。