完全背包问题c++

完全背包问题是一种经典的动态规划问题，可以用以下的C++代码实现：

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

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

    // dp[i][j]表示前i个物品，背包容量为j时的最大价值
    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 >= w[i-1]) {
                dp[i][j] = max(dp[i-1][j], dp[i][j-w[i-1]]+v[i-1]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    cout << dp[n][W] << endl;
    return 0;
}

其中，$n$ 表示物品的个数，$W$ 表示背包的容量，$w$ 表示每个物品的重量，$v$ 表示每个物品的价值。动态规划的转移方程为：

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

其中，$dp[i][j]$ 表示前 $i$ 个物品，背包容量为 $j$ 时的最大价值，$dp[i-1][j]$ 表示不选第 $i$ 个物品，$dp[i][j-w[i-1]]+v[i-1]$ 表示选第 $i$ 个物品。

最后输出 $dp[n][W]$ 即可得到最大价值。