完全背包问题c++代码

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
    vector<int> dp(W + 1, 0);

    for (int i = 0; i <= W; i++) {
        for (int j = 0; j < n; j++) {
            if (wt[j] <= i) {
                dp[i] = max(dp[i], dp[i - wt[j]] + val[j]);
            }
        }
    }

    return dp[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;
}

其中，`W` 表示背包的容量，`wt` 和 `val` 分别表示物品的重量和价值，`n` 表示物品的数量。`dp` 数组表示当前容量下能够获得的最大价值。通过两层循环，不断更新 `dp` 数组，最终返回 `dp[W]` 表示容量为 `W` 时能够获得的最大价值。