分支限界法求解01背包问题c++

分支限界法是一种用于解决优化问题的搜索算法，常用于动态规划问题如0/1背包问题。对于01背包问题，给定一组物品，每个物品有自己的重量w[i]和价值v[i]，背包容量为W，我们需要决定是否选择某个物品放入背包，使得总价值最大。

在C++中使用分支限界法求解01背包问题的一般步骤如下：

1. 定义状态：使用二维数组dp[i][j]表示前i个物品中有j单位重量的最大价值。初始化边界条件：dp[0][0]=0，表示空背包的价值。

2. 动态规划：从第一个物品开始遍历，对于每个物品i，有两种选择：放（取）或不放。如果放，则更新dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])；如果不放，则dp[i][j] = dp[i-1][j]。这里使用了贪心策略（即当前物品价值大于剩余价值则取）。

3. 枝剪（剪枝）：在递归过程中，当发现包含当前物品后的总重量超过背包容量时，由于剩余空间无法再放下其他物品，所以可以直接跳过这部分搜索，避免浪费计算资源。

4. 返回结果：最终的结果就是dp[n][W]，其中n是物品的数量。

#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 j = 1; j <= W; ++j) {
            if (wt[i - 1] <= j) {
                dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[n][W];
}