[动态规划系列] —— 背包DP之完全背包[通俗易懂]

小小码 • 2023-08-10 09:30 • 未分类 • 阅读 121

大家好，我是考100分的小小码，祝大家学习进步，加薪顺利呀。今天说一说[动态规划系列] —— 背包DP之完全背包[通俗易懂],希望您对编程的造诣更进一步.

完全背包问题

有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]