枚举法求解0-1背包问题c++

枚举法是一种求解0-1背包问题的经典动态规划算法。在C++中，它通常通过遍历所有可能的物品组合来寻找最优解。以下是简单的步骤：

1. 定义一个二维数组`dp[i][w]`，其中`i`表示当前考虑的物品索引，`w`表示剩余的背包容量。`dp[i][w]`表示在前`i`个物品中选择，总价值能装满`w`容量背包的最大值。

2. 初始化：对于每个物品`i`，如果背包容量`w`足够大，包含该物品的价值`val[i]`会比不包含更大，所以`dp[i][w] = max(val[i], dp[i-1][w])`；否则，不包含物品，`dp[i][w] = dp[i-1][w]`。

3. 遍历过程：从第一个物品开始到所有物品，对于每一个物品，比较包含它的价值和不包含它的价值，取较大者。

4. 结果：当遍历完整个物品列表后，`dp[n][W]`就是最大价值，其中`n`是物品总数，`W`是背包容量。

#include <iostream>
using namespace std;

int knapsack(int W, int wt[], int val[], int n) {
    // 创建一个二维数组存储动态规划结果
    int dp[n+1][W+1];

    // 逐步填充dp数组
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                dp[i][w] = 0;
            else 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 val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val)/sizeof(val[0]);

    cout << "Max value in the knapsack is: " << knapsack(W, wt, val, n);

    return 0;
}