c++编程实现动态规划法求解0-1背包问题

下面是C++代码实现动态规划法求解0-1背包问题：

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

const int MAX_N = 1000;
const int MAX_W = 10000;

int n, W;
int w[MAX_N], v[MAX_N];
int dp[MAX_N + 1][MAX_W + 1];

int main()
{
    cin >> n >> W;
    for(int i=0; i<n; i++) cin >> w[i] >> v[i];

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<=W; j++)
        {
            if(j < w[i]) dp[i+1][j] = dp[i][j];
            else dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i]);
        }
    }

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

    return 0;
}

其中，$n$表示物品的数量，$W$表示背包的容量，$w_i$和$v_i$分别表示第$i$个物品的重量和价值，$dp[i][j]$表示前$i$个物品中，背包容量为$j$时的最大价值。

在代码中，我们使用双重循环来计算每个状态的最大价值。如果当前物品的重量大于背包容量，则不选择这个物品，即$dp[i+1][j] = dp[i][j]$；否则，我们可以选择这个物品或不选择这个物品，即$dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])$，其中$dp[i][j-w[i]]+v[i]$表示选择这个物品后的总价值。

最终，$dp[n][W]$即为所求的最大价值。