- 问题描述
有 n 个零件，每个零件可以从 m 个供应商中选择。每个供应商提供零件的价格和重量不同。要求在总价格不超过预算 C 的前提下，选择供应商组合使总重量最小。
1.1 解空间
解空间由所有可能的供应商选择组合构成：
每个零件 i 有 m 种选择（供应商 1 到 m）
解是一个长度为 n 的向量 (x₁, x₂, ..., xₙ)
每个 xᵢ ∈ {1, 2, ..., m}
总解数为 mⁿ 种可能
示例（n=3, m=2）：
1.2 解空间树
这是一个 m 叉树，深度为 n：
树结构：
根节点：空选择
第 i 层：对第 i 个零件的选择
每个节点有 m 个子节点（对应 m 个供应商）
叶子节点：完整的选择方案
示例（n=3, m=2）：
text
根(第0层)
/
选供应商1 选供应商2(第1层-零件1)
/ \ /
选1 选2 选1 选2(第2层-零件2)
/ \ / \ / \ /
1 2 1 2 1 2 1 2(第3层-零件3)
(叶子节点-完整方案)
1.3 结点状态值
在遍历过程中，每个结点记录：
当前总价格：已选零件的价格总和
当前总重量：已选零件的重量总和
当前最优解重量（全局变量）：目前找到的最小重量
当前选择路径：已做的供应商选择
剪枝条件：
价格约束剪枝：如果当前总价格 > 预算 C，剪枝
乐观估计剪枝：如果当前重量 + 剩余零件最小可能重量 ≥ 当前最优重量，剪枝
- 对回溯算法的理解
核心思想
回溯法是系统性的深度优先搜索，在解空间树中探索所有可能解，通过剪枝提高效率。
算法框架
python
def backtrack(当前状态):
if 到达叶子节点: # 找到完整解
更新最优解
return
for 所有可能选择:if 约束条件满足: # 剪枝做选择backtrack(新状态)撤销选择 # 回溯
关键特性
系统性搜索：遍历所有可能组合
深度优先：沿一条路径到底再返回
剪枝优化：提前排除无效分支
状态恢复：撤销选择回到之前状态
适用场景
组合优化问题（如背包、排列、子集）
约束满足问题（如N皇后、数独）
需要找出所有解或最优解的问题
优点与局限
优点：
能找到精确最优解
框架清晰，易于实现
通过剪枝可以处理中等规模问题
局限：
时间复杂度指数级（最坏情况）
不适合大规模问题
需要设计有效的剪枝策略
与其它算法对比
vs 贪心：回溯能找最优解，贪心可能只是近似
vs 动态规划：回溯更通用，但DP更高效（对重叠子问题）
vs 分支限界：回溯深度优先，分支限界通常最佳优先
总结
回溯法通过"尝试-回溯"机制搜索解空间，是解决组合优化问题的经典方法。最小重量机器设计问题通过构造 m 叉解空间树，利用价格约束和重量估计进行剪枝，能有效找到最优供应商组合。