题解 | #完全背包#

class Solution:
    def knapsack(self , v: int, n: int, nums: List[List[int]]) -> List[int]:
        result = [0, 0]
		
        dp = [0] * (v + 1)
        # 一、背包能够装备的最高价值
        for i in range(1, v + 1):
            for j in range(len(nums)):
                if i - nums[j][0] >= 0:
                    dp[i] = max(dp[i], dp[i - nums[j][0]] + nums[j][1])
        
        result[0] = dp[-1]

        dp = [0] * (v + 1)
        # 二、背包刚好能够装备的最高价值：
        for i in range(1, v + 1):
            for j in range(len(nums)):
                # 1、（最关键的情况）情况一正好为空包再加新物品时
                if i - nums[j][0] == 0:
                    dp[i] = max(dp[i], nums[j][1])
                # 2、情况二为不空包情况时加新物品时
                elif i - nums[j][0] > 0 and dp[i - nums[j][0]] != 0:
                    dp[i] = max(dp[i], dp[i - nums[j][0]] + nums[j][1])

        result[1] = dp[-1]

        return result