回溯法：最小重量机器设计问题（python解决）

回溯法：最小重量机器设计问题（python解决）

问题描述：
最小重量机器设计问题：设某一机器由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 = 3 # 零件数量
m = 2 # 供应商数量
p = 60 # 不应超过的价格w = [[12, 15], [23, 24], [78, 70]] # 供应商j处购得的部件 i 的重量
c = [[8, 6], [13, 9], [14, 25]] # 相应的价格min_weight = 10000
bast_choose = [None]*3cur_choose = [None]*10
cur_weight = 0
cur_price = 0def backtrack(t):
# 此处的t代表每一次遍历i供应商的零件global cur_weight, cur_price, cur_choose, min_weight, p, w, cif t == n:# 遍历到叶子结点if cur_weight < min_weight:min_weight = cur_weightfor j in range(n):bast_choose[j] = cur_choose[j] + 1returnelse:for i in range(m): # 遍历供应商cur_choose[t] = icur_weight += w[t][i]cur_price += c[t][i]if cur_weight < min_weight and cur_price <= p:# 该供应商的重量小于局部最优解 同时价格满足要求 则遍历其子树backtrack(t+1)cur_weight -= w[t][i]cur_price -= c[t][i]cur_choose[t] = 0def main():backtrack(0)print('最小的重量是:%d'%min_weight)print('最佳选择是:',bast_choose)if __name__ == '__main__':main()

运行截图：