"""2,3,2,4四个月份,每个月的需求量是这些,每生产一次消耗3,每生产一个消耗1,每保存一个一个月消耗0.5.因为最后全部消耗完,所以固定成本共11无法避免"""need = [0, 2, 3, 2, 4]sumneed = sum(need)a = [[0 for i in range(sumneed + 1)] for j in range(len(need) + 1)]# b存储上一个结点b = [[0 for i in range(sumneed + 1)] for j in range(len(need) + 1)]"""a[x][y]表示x月底剩下y件产品时的花费"""a[0][0] = 0for i in range(1, len(a[0])):   a[0][i] = 0xfffffffor i in range(1, len(need)):   for j in range(0, sumneed + 1):      # 第i个月不生产      a[i][j] = 0xffffff      # 本月不生产,则上月剩余j+need[i]件,需要库存j件      if j + need[i] <= sumneed:         a[i][j] = a[i - 1][j + need[i]] + j * 0.5         b[i][j] = (j + need[i], "本月不生产")      # 本月生产k件,本月剩余j件,则上月剩余j+need[i]-k      for k in range(0, j + 1 + need[i]):         if j + need[i] - k <= sumneed:            t = j * 0.5 + 3 + a[i - 1][j + need[i] - k]            if a[i][j] > t:               a[i][j] = t               b[i][j] = (j + need[i] - k, "本月生产{}件".format(k))i, j = len(need) - 1, 0while i > 0:   print(a[i][j], b[i][j])   i, j = i - 1, b[i][j][0]print("算上每件的成本,共需要{}花费".format(a[len(need) - 1][0] + sumneed))

g = [[0, 10, 20, 30, 40, 50],     [12, 0, 18, 30, 25, 21],     [23, 19, 0, 5, 10, 15],     [34, 32, 4, 0, 8, 16],     [45, 27, 11, 10, 0, 18],     [56, 22, 16, 20, 12, 0]]citycnt = 6# 有6个城市,用000000-111111表示状态,0表示未访问该城市,1表示访问过该城市statecnt = 1 << citycnt"""用a[state][lastCity]表示状态为state时的最后一个城市是谁用b[state][lastCity]记录上一个城市是谁,用于回溯找出一条路径"""a = [[0xfffffff for i in range(citycnt)] for i in range(statecnt)]b = [[0 for i in range(citycnt)] for i in range(statecnt)]a[1][0] = 0  # 只需从第一个城市出发,将第一个城市置为0,其他城市置为无穷for i in range(2, statecnt):   for j in range(citycnt):      if (i & (1 << j)) == 0: continue  # 如果状态i不包含城市j,那么状态i的最后一个城市不可能是j,所以continue      for k in range(citycnt):         if i & (1 << k) == 0 or j == k: continue         dis = a[i - (1 << j)][k] + g[k][j]         if dis < a[i][j]:            a[i][j] = dis            b[i][j] = (i - (1 << j), k)now, state = 0, statecnt - 1for i in range(citycnt):   if a[state][i] + g[i][0] < a[state][now] + g[now][0]:      now = iprint("最短距离为", a[state][now]+g[now][0])while state != 1:   print("{}({})".format(now, bin(state)), end="=>")   (state, now) = b[state][now]