北航算法作业二

生产调度问题

"""
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] = 0
for i in range(1, len(a[0])):
   a[0][i] = 0xffffff
for 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, 0
while 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))

在这个问题中,优化的空间很大.a[x][y]可以只依赖于a[x-1]层的两个数,而不用考虑中间的数.因为这里面有一个贪心:如果本月生产,那么尽量上个月剩余为0.

汉密尔顿路

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 - 1
for i in range(citycnt):
   if a[state][i] + g[i][0] < a[state][now] + g[now][0]:
      now = i
print("最短距离为", a[state][now]+g[now][0])
while state != 1:
   print("{}({})".format(now, bin(state)), end="=>")
   (state, now) = b[state][now]

 汉密尔顿回路和汉密尔顿路是等价的,中间只是多了一条回边.

此算法复杂度为O(2^n*n^2).