齐全背包问题
有 n 个物品,1 个容量 v 的背包,第 i 个物品体积是 volume[i],价值是 value[i],问将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大,每个物品能够应用有限次。
如果你浏览过我的上一篇文章 01 背包,那么齐全背包问题的代码只须要在其根底之上作很小的改变。在 01 背包的状态压缩中咱们提到,j 值须要向左增长,保障可能正确的援用到上一次状态的后果。
而若是 j 值向右增长,那么咱们援用的“上一次状态”实际上是曾经被更新的以后次的状态,这一步的含意指以后物品能够被反复抉择,而这恰好就是齐全背包问题。
def solution(n, v, volume, value):
status = [0]*(v+1)
for i in range(1, n+1):
for j in range(volume[i-1], v+1): # 相比于 01 背包,只有这一行做了改变
status[j] = max(status[j], value[i-1] + status[j-volume[i-1]])
return status[v]
如果下面的解释还没有了解,持续向下看,但请确保你曾经了解了 01 背包问题。
首先回顾 01 背包中 status[i][j] = max(status[i-1][j], value[i-1] + status[i-1][j-volume[i-1]])
的含意。
在状态转移的过程中,咱们思考前 i - 1 件物品的状态,和是否抉择第 i 件物品,保障了 01 背包问题中每个物品只能抉择一次的个性。
而对于齐全背包问题,每件物品能够有限应用,也就是对于第 i 件物品,咱们能够反复抉择,在这种状况下,status[i][j]
能够由 status[i][j-volume[i-1]]
转移而来。
def solution(n, v, volume, value):
status = [[0]*(v+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, v+1):
if j - volume[i-1] >= 0:
status[i][j] = max(status[i-1][j], value[i-1] + status[i][j-volume[i-1]]) # 相比于 01 背包,只有这一行做了改变
else: status[i][j] = status[i-1][j]
return status[n][v]
同样的,咱们对齐全背包版本的代码作状态压缩。
def solution(n, v, volume, value):
status = [0]*(v+1)
for i in range(1, n+1):
for j in range(1, v+1):
if j - volume[i-1] >= 0:
status[j] = max(status[j], value[i-1] + status[j-volume[i-1]]) # 相比于 01 背包,只有这一行做了改变
else: status[j] = status[j]
return status[v]
咱们会发现状态压缩后,齐全背包和 01 背包的状态转移方程统一,思考 01 背包的 j 为何要向左增长?是因为 01 背包中须要尚未更新的status[j-volume[i-1]]
,也就是status[i-1][j-volume[i-1]]
。
而齐全背包须要的是status[i][j-volume[i-1]]
,即曾经更新的status[j-volume[i-1]]
,所以 j 须要向右增长,再对分支构造做简略的优化,能够失去最终版本齐全背包问题的代码。
def solution(n, v, volume, value):
status = [0]*(v+1)
for i in range(1, n+1):
for j in range(volume[i-1], v+1):
status[j] = max(status[j], value[i-1] + status[j-volume[i-1]])
return status[v]
这也就是本文最开始给出的代码。
之所以该问题被称作齐全背包,其起因在于对于每一样物品能够应用有限次。在咱们遇到的题目中,往往是齐全背包问题的变体,咱们须要学会如何将题目转换为经典的齐全背包问题。
相干题目:零钱兑换 II,组合总和 Ⅳ。