⚠️ 那个 40 是怎么填出来的
一件只拿一次,还是能拿多次
只一次
拿多次
回到「贪心」那条路线(`l1_algo_07_n06`)里的三件东西:(重6值30)、(重5值20)、(重5值20),容量 10。当时只说了最优解是 40,现在把它填出来:
def knap1d(items, cap):
dp = [0] * (cap + 1)
for w, v in items:
for c in range(cap, w - 1, -1):
if dp[c - w] + v > dp[c]:
dp[c] = dp[c - w] + v
return dp
print(knap1d([(6, 30), (5, 20), (5, 20)], 10)[10])
全部评论