完全背包问题

完全背包问题 Python描述

"""完全背包问题"""
from functools import cache

# 有n种物品，第i种物品的体积为w[i]，价值为v[i]，每种物品无限次重复选
# 求体积和不超过 capacity 时的最大价值

"""选或者不选"""
# 选：剩余容量减少w[i]
# 不选：容量不变

"""子问题"""
# 在剩余容量为 c 时，从前 i 种物品中得到的最大价值和

"""下一个子问题"""
# 不选：在剩余容量为 c 时，从前 i-1 种物品中得到的最大价值和
# 选一个：在剩余容量为 c - w[i] 时，从前 i 种物品中得到的最大价值和

"""状态转移方程"""
# 注意！！！！如果选的话是可以重复选的，所以不必i-1，继续用i递归下去
# dfs(i, c) = max(dfs(i-1, c), dfs(i, c-w[i]) + v[i])

class Solution:
    def complete_knapsack(self, capacity: int, weights: list[int], values: list[int]) -> int:
        n = len(weights)
        @cache
        def dfs(i, c):
            # 越界
            if i < 0:
                return 0
            # 背包满了
            if c < weights[i]:
                # 不选
                return dfs(i-1, c)
            return max(dfs(i-1, c), dfs(i, c - weights[i]) + values[i])
        return dfs(n-1, capacity)