0/1 背包问题使用最小成本分支界定法

0/1 背包问题是一个经典的组合优化问题，给定一组物品，每个物品都有重量和价值，目标是选择这些物品的一个子集，以使总价值最大化，同时确保总重量不超过给定容量。

最小成本分支定界法 (LCBB) 是一种用于解决组合优化问题的技术，包括 0/1 背包问题。它结合了分支定界法的原理和指导解决方案空间探索的启发式方法。

让我们来实现代码

代码

输出

说明

物品结构

Item 是一个用户定义的结构，具有两个属性：重量和价值。Item 的每个实例都代表背包问题中的一个物品。

比较函数

compareItems 是一个根据物品的价值重量比比较两个物品的函数。它接受两个 Item 对象作为参数，并返回一个布尔值，指示第一个 Item 是否比第二个具有更高的百分比。此函数用作物品排序的判据。

计算上限

calculateUpperBound 估计搜索树中给定节点的上限。它将物品列表、剩余容量、当前重量、当前价值和当前物品索引作为参数。该函数遍历剩余物品，将其价值添加到上限，直到容量耗尽或所有物品都被考虑。如果下一个物品不能完全放入，它还会添加其分数部分。

背包分支定界法

knapsackBnB 是分支定界算法的主要递归函数。它接受表示背包当前状态的参数、搜索树中的当前节点、当前已知最佳解决方案 (maxValue) 以及一个向量 (selected items) 以跟踪选定物品的索引。该函数在每个节点探索两个分支：一个包含当前物品，一个排除当前物品。通过将节点的上限与当前已知最佳解决方案进行比较来执行剪枝。如果上限较小，则剪枝该分支。

基本情况处理

当所有物品都被考虑（currentIndex == items.size()）或背包容量已满（current weight == capacity）时，达到递归的基本情况。在基本情况下，函数检查当前解决方案是否优于当前已知最佳解决方案 (maxValue)。如果是，则更新 maxValue，并将选定物品的索引存储在 selectedItems 向量中。

物品排序

在开始算法之前，使用 compareItems 函数根据价值重量比对物品进行排序。排序对于最小成本分支定界方法至关重要，因为它决定了节点探索的顺序。

主函数

在主函数中，定义了一组示例物品和背包容量。使用 compareItems 函数对物品进行排序，以根据成本优先进行探索。使用排序后的物品和其他必要参数调用 knapsackBnB 函数。

输出显示

算法执行完成后，显示最佳价值和选定物品的索引。选定物品代表 0/1 背包问题的解决方案。

让我们讨论一下代码的时间和空间复杂度

时间复杂度

算法的时间复杂度受搜索树中探索的节点数量的影响。

最坏情况：在最坏情况下，算法会探索所有可能的物品组合，对应于深度为 n（物品数量）的二叉树中的节点数量。最坏情况时间复杂度是指数级的，O(2^n)。

平均情况：平均时间复杂度取决于分支定界剪枝的效率。根据价值重量比对物品进行排序需要 O(n log n) 时间。

由于剪枝，平均情况时间复杂度通常优于最坏情况，但在某些情况下仍可能是指数级的。

空间复杂度

空间复杂度由递归调用、栈和使用的数据结构所需的额外空间决定。

栈空间：递归的深度对应于搜索树的高度。

在最坏情况下，算法可能使用与树高成比例的栈空间，O(n)。

额外数据结构

selectedItems 向量用于存储选定物品的索引。向量所需的空间与选定物品的数量成正比，最多为 n。物品排序也需要额外空间，但通常会被递归栈空间所掩盖。

总而言之

由于栈空间和 selectedItems 向量，整体空间复杂度为 O(n)。

0/1 背包问题的应用

融资

投资组合优化，其中物品代表金融资产，背包代表预算或风险承受能力。

资源分配

分配时间、预算或人力等资源以最大化总价值。

物流

选择代表货物的具有重量和价值的物品，以优化运输中的货物装载。

解决此问题的另一种技术

动态规划方法：0/1 背包问题可以使用动态规划有效解决。动态规划方法涉及构建一个表来存储中间解决方案并逐步解决更大的子问题。此方法的时间复杂度为 O(nW)，其中 n 是物品数量，W 是背包容量。

分数背包问题

在分数背包问题中，物品可以被分割以最大化总价值。与 0/1 背包问题相比，这个问题通常更容易解决。贪婪算法通常用于分数背包问题，其中物品按其价值重量比排序，并选择比率最高的物品，直到背包装满。