分支限界法0-1背包问题C++实验代码

分支限界法是一种解决优化问题的搜索算法，尤其适用于整数线性规划问题，如0-1背包问题。在0-1背包问题中，给定一组物品，每个物品有自己的重量和价值，目标是在不超过背包容量的情况下，选择最优组合使得总价值最大。

这是一个经典的动态规划问题，也可以通过分治策略结合回溯的思想用分支限界法求解。下面是一个简单的C++代码示例：

#include <vector>
#include <climits>

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);
    return 0;
}

在这个例子中，`knapsack`函数使用了二维动态规划数组dp，其中dp[i][w]表示前i个物品、背包容量为w时的最大价值。核心部分就是比较当前物品加入背包是否能带来更大的价值。