C++ DP背包问题

C++中的DP背包问题是一个经典的动态规划问题，用于解决在给定背包容量和一组物品的情况下，如何选择物品放入背包以使得总价值最大化的问题。下面是一个简单的示例代码来解决背包问题：

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

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

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

    return dp[n][W];
}

int main() {
    int W = 50; // 背包容量
    vector<int> wt = {10, 20, 30}; // 物品重量
    vector<int> val = {60, 100, 120}; // 物品价值
    int n = wt.size(); // 物品数量

    int maxVal = knapsack(W, wt, val, n);
    cout << "Max value: " << maxVal << endl;

    return 0;
}

这段代码使用二维数组`dp`来保存每个子问题的最优解，其中`dp[i][w]`表示在前`i`个物品中选择，背包容量为`w`时的最大价值。通过遍历每个物品和背包容量，根据当前物品的重量和价值来更新`dp`数组。最后返回`dp[n][W]`即为问题的最优解。