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

在C++中，使用分支限界法解决01背包问题，通常涉及动态规划和广度优先搜索（BFS）或深度优先搜索（DFS）。以下是简化版的代码示例：

#include <iostream>
#include <vector>
#include <queue>

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(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
            } 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(); // 物品种类数

    cout << "最大价值: " << knapsack(W, wt, val, n) << endl;
    return 0;
}

这个代码首先初始化了一个二维数组`dp`来存储每种情况下的最优解，然后通过嵌套循环遍历所有物品和背包容量，计算包括当前物品和不包括当前物品在内的最大价值。在分支限界法中，我们通常不需要显式地使用BFS或DFS，因为动态规划本身就实现了类似的过程。