题解 | #01背包#

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        #定义前i个、总体积为j的物品的总质量,等价于dp=[0*(V+1)]
        dp=[0 for _ in range(V+1)]
        for i in range(1,n+1):
            for j in range(V,0,-1):
                if(j>=vw[i-1][0]):            #判断第i件是否可拿
                    #判断当拿取到总质量j时，是不拿第i件时质量最重，还是拿了第i件时质量最重
                    dp[j]=max(dp[j],dp[j-vw[i-1][0]]+vw[i-1][1])                       
        return dp[V]