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

分支限界法是一种用于解决组合优化问题的搜索算法，特别适用于动态规划问题，如0/1背包问题。在这个问题中，给定一组物品，每个物品有自己的价值`v[i]`和重量`w[i]`，有一个背包能承受的最大重量`W`。目标是在不超过背包容量的前提下，选择能够获得最大价值的一组物品。

在C++中，可以使用分支限界法通过递归的方式实现。基本步骤如下：

1. 定义状态：用二维数组`dp[i][j]`表示前`i`件物品，总重量不超过`j`时可以获得的最大价值。初始化`dp[0][0] = 0`。

2. 递归函数：对于第`i`件物品，有两个选择，要么不选（`dp[i][j] = dp[i - 1][j]`），要么选（如果`w[i] <= j`则`dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i])`）。这个过程就是“分支”：选择是否包含当前物品。

3. 上界剪枝：由于动态规划的性质，对`dp`数组的计算有上界限制，即不可能超过`W`。因此，当`j < w[i]`时，确定不会选择当前物品，可以直接跳过递归。

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

以下是简化的C++代码片段示例：

#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];
}