分支限界法求解货郎担问题

分支限界法（Branch and Bound）是一种用于求解组合优化问题的搜索算法，特别适用于解决像货郎担问题（Knapsack Problem）这样的整数线性规划问题。货郎担问题是一个经典的背包问题，目标是在给定的物品重量和价值约束下，选择物品使得总价值最大或总重量最小。

分支限界法的工作原理分为以下几个步骤：

1. **初始状态**：从问题的最原始状态开始，通常是最小子集或空背包。

2. **分支操作**：对于每个可能的决策（如是否选取某个物品），算法会创建一个新的子问题，并继续探索。

3. **限界函数**：利用已知的最优解信息（上界或下界），判断当前子问题是否有解，如果明显不满足目标（例如总重量超过背包容量），就直接剪枝，不再深入搜索。

4. **搜索策略**：通常采用广度优先搜索（BFS）或深度优先搜索（DFS），并根据问题的特性和搜索空间的特点可能调整。

5. **回溯**：如果所有子问题都无法达到目标，会选择最优解返回，这是通过回溯搜索过程实现的。

6. **更新最优解**：每次找到一个更好的解时，都会更新全局最优解。