使用分支限界法解决01背包问题c++简易

分支限界法是一种搜索算法，常用于求解组合优化问题，如背包问题。对于01背包问题（即每个物品只能取一次），我们可以使用动态规划结合回溯的思想来实现。下面是一个简单的C++代码示例：

#include <iostream>
#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));

    // 动态规划初始化
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (int w = 1; w <= W; w++) {
        dp[0][w] = -INT_MAX;
    }

    // 递推过程
    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[i][w]`表示在容量w的情况下考虑前i个物品的最大价值。通过遍历所有可能的情况，我们选择最优的决策路径，直到达到背包容量上限。