01背包

题目

传送门

思路

为了便于描述，我们使用符号\((n, v)\)来表示有n件物品时，背包容积为v时，能装的最大价值

对于第i个物品，有两种选择：

不装，此时\((i, v) = (i - 1, v)\)
装，此时\((i, v) = (i - 1, v - v_i) + w_i\)，这里的\(v_i\)代表第i件物品的体积，\(w_i\)代表第i件物品的重量。这里之所以要将背包的容积减掉\(v_i\)是因为如果要将物品i装进去，必须要确保还有\(v_i\)这么多的空间

我们得到状态转移方程

\[\left( i,v\right) =\begin{cases}\left( i-1,v\right) \\ \left( i-1,v-v_{i}\right) +w_{i}\end{cases} \]

代码

递归加缓存版本

from functools import lru_cache

# 不限制缓存大小
@lru_cache(None)
def f(i: int, j: int) -> int:
    # 对于前i个物品，背包容量为j的时候，最多能装的价值

    # 背包容量等于0，或者没有任何物品，只能装0
    if j == 0 or i == -1:
        return 0

    # 如果第i件物品的体积超过背包的容积，只能不装
    if VW[i][0] > j:
        return f(i - 1, j)
        
    # 每次有两种选择
    # 1. 不装这件物品，也就是f(i - 1, j)
    # 2. 装这件物品，也就是f(i - 1, j - VW[i][0]) + VW[i][1]
    return max(f(i - 1, j), f(i - 1, j - VW[i][0]) + VW[i][1])


class Solution:
    def knapsack(self, V: int, n: int, vw: List[List[int]]) -> int:
        global VW
        VW = vw
        return f(n-1, V)

二维dp

class Solution:
    def knapsack(self, V: int, n: int, vw: List[List[int]]) -> int:
        dp = [[0] * (V + 1) for i in range(n + 1)]
        vw = [[]] + vw

        # i代表物品个数，j代表背包容积
        for i in range(1, n + 1):
            for j in range(1, V + 1):
                if vw[i][0] > j:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vw[i][0]] + vw[i][1])

        return dp[n][V]

一维dp

class Solution:
    def knapsack(self, V: int, n: int, vw: List[List[int]]) -> int:
        dp = [0] * (V + 1)
        vw = [[]] + vw

        for i in range(1, n + 1):
            for j in reversed(range(1, V + 1)):
                if vw[i][0] <= j:
                    dp[j] = max(dp[j], dp[j - vw[i][0]] + vw[i][1])

        return dp[V]