使用分支限界法解决01背包问题c++要求代码通俗易懂

分支限界法（Branch and Bound）是一种用于求解优化问题（如背包问题）的搜索算法，它通过不断剪枝（排除不可能得到最优解的部分）来提高效率。对于01背包问题，我们需要决定物品是否放入背包，以及分配的最大价值，以达到总价值最大化。

以下是使用分支限界法求解01背包问题的一个简单C++代码示例：

#include <vector>
#include <algorithm>

// 物品结构体，包含值和重量
struct Item {
    int value;
    int weight;
};

// 比较函数，用于排序
bool compare(const Item& a, const Item& b) {
    return a.value / a.weight > b.value / b.weight; // 按价值密度排序
}

// 动态规划辅助函数，计算包含某物品后的背包最大价值
int knapsackHelper(int capacity, std::vector<Item>& items, int index, bool taken[]) {
    if (index == items.size() || capacity == 0)
        return 0;

    int include = items[index].value + knapsackHelper(capacity - items[index].weight, items, index + 1, taken);
    int exclude = knapsackHelper(capacity, items, index + 1, taken);

    taken[index] = include > exclude;
    return taken[index] ? include : exclude;
}

// 主函数
int knapsack(int capacity, std::vector<Item>& items) {
    std::sort(items.begin(), items.end(), compare); // 先按价值密度排序

    bool taken[items.size()];
    memset(taken, false, sizeof(taken)); // 初始化所有物品未选中
    return knapsackHelper(capacity, items, 0, taken);
}

在这个代码中，`knapsack`函数是主入口，`knapsackHelper`是一个递归辅助函数，用于遍历所有可能的选择。我们首先将物品按照价值密度排序，然后从最高价值密度的开始尝试选择和不选择该物品，剪枝掉那些显然不会产生更大收益的情况。