共计 1708 个字符，预计需要花费 5 分钟才能阅读完成。
齐全背包问题
有 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，组合总和 Ⅳ。