四项一起对得上吗
运行下面这段程序:
def greedy(cs, t):
n = 0
for c in cs:
while t >= c:
t -= c
n += 1
return n
def best(cs, t):
INF = 10 ** 9
dp = [0] + [INF] * t
for a in range(1, t + 1):
for c in cs:
if c <= a and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1
return dp[t]
def sched(iv, key):
end = -1
n = 0
for s, e in sorted(iv, key=key):
if s >= end:
n += 1
end = e
return n
def wait(order):
t = 0
s = 0
for x in order:
t += x
s += t
return s
ok = (greedy([25, 10, 5, 1], 63) == 6
and best([4, 3, 1], 6) == 2
and sched([(1, 4), (2, 3), (3, 5), (0, 7), (5, 6), (6, 8)], lambda t: t[1]) == 4
and wait(sorted([4, 1, 3, 2])) == 20)
print(ok)
全部评论