问题描述：
最小重量机器设计问题：设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设 w[i][j] 是从供应商j处购得的部件 i 的重量， c[i][j]是相应的价格。试设计一个算法，给出总价格不超过 p 的最小重量机器设计。
利用回溯法求解问题，首先可以为该题的二维数组w、c赋初值，不妨令n=3，m=2、p=60。构造回溯法中的解空间树，大概如下：
根据回溯法的要求，进行的是深度遍历，同时满足重量尽可能小，价格不能超过p。
明确以上要求后便可以进行代码的编写：
# coding = 'utf-8'
# python
# 最小重量机器设计问题：设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。
# 设 w[i][j] 是从供应商j处购得的部件 i 的重量， c[i][j] 是相应的价格。
# 试设计一个算法，给出总价格不超过 p 的最小重量机器设计
# 限定：价格不超过p 重量尽可能小
n = # 零件数量
m = # 供应商数量
p = # 不应超过的价格
w = [[, ], [, ], [, ]] # 供应商j处购得的部件 i 的重量
c = [[, ], [, ], [, ]] # 相应的价格
min_weight =
bast_choose = [None]*
cur_choose = [None]*
cur_weight =
cur_price =
def backtrack(t):
# 此处的t代表每一次遍历i供应商的零件
global cur_weight, cur_price, cur_choose, min_weight, p, w, c
if t == n:
# 遍历到叶子结点
if cur_weight < min_weight:
min_weight = cur_weight
for j in range(n):
bast_choose[j] = cur_choose[j] +
return
else:
for i in range(m): # 遍历供应商
cur_choose[t] = i
cur_weight += w[t][i]
cur_price += c[t][i]
if cur_weight < min_weight and cur_price <= p:
# 该供应商的重量小于局部最优解 同时价格满足要求 则遍历其子树
backtrack(t+)
cur_weight -= w[t][i]
cur_price -= c[t][i]
cur_choose[t] =
def main():
backtrack()
print('最小的重量是:%d'%min_weight)
print('最佳选择是:',bast_choose)
if __name__ == '__main__':
main()
运行截图：
