01背包问题 —— 算法设计与分支限界法

分支限界

问题背景

一组包含N个不同物品的集合，在每个物品都有特定的重量与价值属性的前提下，并假设有一个固定容量的背包，请问如何在不超过背包容量限制的情况下使装入其中的这些物品的价值总和最大化？
特别指出，在0-1背包问题中，请记住每个物品只有两种状态：完全装入或完全不装入，并且不允许将一个物品拆分成更小的部分放入背包中。对于允许将某些物体的一部分放入情况，则通常统称为"分数背包"问题或"可分物"问题。

---

分支限界

注

• 与回溯法的区别

求解目标：
回溯算法的主要任务在于确定满足特定约束的所有可行解决方案。相比之下, 分支限界方法（BCP）的主要目的是确定一个满足给定约束的基本可行解决方案. 该方法不仅能够找到基本可行方案, 在某些情况下还能优化这些方案的质量.

搜索方式的不同：
回溯法主要通过深度优先的方法进行解空间树的搜索操作，而分支限界法则不仅采用了广度优先策略进行搜索，并且还能够采用最小耗费优先策略来完成特定问题的求解过程。

---

分支限界下的01背包问题

思想
基于优先级队列机制，在逆向搜索算法中对目标成本进行优化求解。具体而言：
首先根据物品单位价值降序排列。
采用大根堆数据结构组织物品信息。