分支限界法求解01背包的c++完整代码

分支限界法是一种用于解决组合优化问题的算法策略，它通过剪枝技术避免搜索所有可能的状态，适用于像背包问题这样的动态规划问题。对于01背包问题，我们可以创建一个递归函数来表示状态转移，并结合优先队列来存储待探索的节点。

以下是一个简单的C++实现，假设背包容量为`W`，物品数量为`n`，每个物品的价值为`values[]`，重量为`weights[]`：

#include <vector>
#include <queue>
#include <climits>

using namespace std;

// 背包价值函数
int knapsack(int W, vector<int>& weights, vector<int>& values, int i, int totalWeight) {
    if (i == n || totalWeight >= W)
        return 0; // 如果物品索引超出或重量超过背包，返回0

    // 当前物品选择
    int include = values[i] + knapsack(W, weights, values, i+1, min(totalWeight+weights[i], W));
    
    // 当前物品不选
    int exclude = knapsack(W, weights, values, i+1, totalWeight); 

    return max(include, exclude);
}

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

    cout << "最大价值为: " << knapsack(W, weights, values, 0, 0) << endl;
    return 0;
}

在这个代码中，`knapsack`函数是一个递归函数，`include`代表包含当前物品的情况，`exclude`代表不包含当前物品的情况。我们通过`min(totalWeight+weights[i], W)`来限制后续状态的探索，防止搜索重复路径。