分支界限法 解决0-1背包问题 C/C++代码实现

分支界限算法是一种用于求解最优化问题的搜索策略，它通过剪枝技术减少搜索空间。对于0-1背包问题，这是一个经典的动态规划问题，其中物品有各自的重量和价值，目标是在不超过背包容量的情况下选择物品以最大化总价值。

0-1背包问题的分支界限法通常是通过贪心策略（如最小收益剪枝）结合回溯搜索来实现的。以下是C/C++的一个基本实现框架：

#include <iostream>
#include <vector>

int knapsack(int W, std::vector<int>& wt, std::vector<int>& val, int n) {
    // 动态规划表
    std::vector<bool> dp(n + 1, false);
    std::vector<int> taken(n + 1, 0);

    for (int i = 1; i <= n; ++i) { // 遍历每个物品
        if (wt[i - 1] > W) continue; // 如果当前物品超重则跳过

        // 检查不包含当前物品的情况
        dp[i] = dp[i - 1];

        // 包含当前物品，检查是否比不包含更大
        if (dp[i] < dp[i - 1]) {
            dp[i] = dp[i - 1] + val[i - 1]; // 更新最大值
            taken[i] = 1; // 记录选择了该物品
        }
    }

    return dp[n];
}

// 主函数测试
int main() {
    int W = 50;
    std::vector<int> wt = {10, 20, 30};
    std::vector<int> val = {60, 100, 120};
    int n = wt.size();

    int max_val = knapsack(W, wt, val, n);
    std::cout << "最大价值为: " << max_val << std::endl;

    return 0;
}

这个代码实现了0-1背包问题的解决方案，并使用了一个布尔数组`dp`来存储到第`i`个物品为止的最大价值是否包含当前物品。在回溯过程中，如果包含当前物品的总价值小于不包含，就舍弃包含的路径，这就是剪枝的过程。