有一天，在电梯里，很多人，大家纷纷按了自己想去的楼层
因为电梯一个劲地停，我就想去4楼的能不能在3楼就下，这样在4楼就能少停一次，他们可以走楼梯，牺牲一点个人利益换取集体利益最大化
我想，每个人在电梯里都这么想过
今天将这个问题仔细思考，形式化了一下，发现是一道动态规划问题，解决起来也是十分优美
N层楼，从0到N-1层，给定数组a[N]表示每层楼要下多少人，每个人爬一层楼花费M秒，电梯爬一层楼需要K秒，电梯每停一次花费P秒，问电梯如何停靠才能使得大家等待的总时间尽量短？
import random
N = 16 # N层楼,0~(N-1)层
a = [random.randint(0, 4) for _ in range(N)] # 每层楼有多少个人下电梯
M = 3 # 人爬一层楼需要的时间
K = 1 # 电梯爬一层楼需要的时间
P = 2 # 电梯停一次需要的时间
f = [[0] * N for _ in range(N)]
desc = [['' for __ in range(N)] for _ in range(N)]
for i in range(N):
for j in range(i + 1, N):
f[i][j] = sum(a[i + 1:]) * (j - i) * K + sum(a[j + 1:]) * P
desc[i][j] = '=' * 20
desc[i][j] += '
{}人从{}楼到{}楼因为电梯运行等了{}秒'.format(sum(a[i + 1:]), i, j, sum(a[i + 1:]) * (j - i) * K)
desc[i][j] += '
{}人因为电梯在{}楼停了一次等了{}秒'.format(sum(a[j + 1:]), j, sum(a[j + 1:]) * P)
for k in range(i + 1, j):
f[i][j] += min(k - i, j - k) * M * a[k]
if a[k] > 0:
desc[i][j] += '
{}人从{}楼下电梯去往{}楼因为走楼梯花费{}秒'.format(a[k], i if k - i < j - k else j, k,
min(k - i, j - k) * M * a[k])
g = [(0xfffffff, 0)] * N
g[0] = (0, 0)
for i in range(N):
for j in range(i):
if g[i][0] > g[j][0] + f[j][i]:
g[i] = (g[j][0] + f[j][i], j)
print(g[N - 1])
stop = []
x = N - 1
while x:
stop.append(x)
x = g[x][1]
stop.append(0)
stop = stop[::-1]
print('每层人数', a)
print('停电梯楼层号', stop)
for i in range(1, len(stop)):
print(desc[stop[i - 1]][stop[i]])
运行结果
(334, 14)
每层人数 [1, 1, 1, 0, 3, 1, 3, 0, 3, 0, 2, 2, 1, 2, 2, 2]
停电梯楼层号 [0, 6, 8, 11, 13, 14, 15]
====================
23人从0楼到6楼因为电梯运行等了138秒
14人因为电梯在6楼停了一次等了28秒
1人从0楼下电梯去往1楼因为走楼梯花费3秒
1人从0楼下电梯去往2楼因为走楼梯花费6秒
3人从6楼下电梯去往4楼因为走楼梯花费18秒
1人从6楼下电梯去往5楼因为走楼梯花费3秒
====================
14人从6楼到8楼因为电梯运行等了28秒
11人因为电梯在8楼停了一次等了22秒
====================
11人从8楼到11楼因为电梯运行等了33秒
7人因为电梯在11楼停了一次等了14秒
2人从11楼下电梯去往10楼因为走楼梯花费6秒
====================
7人从11楼到13楼因为电梯运行等了14秒
4人因为电梯在13楼停了一次等了8秒
1人从13楼下电梯去往12楼因为走楼梯花费3秒
====================
4人从13楼到14楼因为电梯运行等了4秒
2人因为电梯在14楼停了一次等了4秒
====================
2人从14楼到15楼因为电梯运行等了2秒
0人因为电梯在15楼停了一次等了0秒