题解 | #01背包#

'''
解题思路：
01背包问题：
1、dp[i][j]定义：前i个物品，背包的最大价值或重量
2、递推公式：
(a) j>=v[i]时，dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
(b) j<v[i]时，dp[i][j] = dp[i-1][j]
3、边界条件：i=0或j=0时，dp[i][j] = 0
特别注意：由于dp多了一行和一列，读v[i]、w[i]时，用下标i-1
'''
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 计算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 , n , vw ):
        # write code here
        #print('V=',V)
        #print('n=',n)
        #print('vw=',vw)

        dp = [[0]*(V+1) for _ in range(n+1)]
        
        for i in range(n+1):
            v_i = vw[i-1][0]
            w_i = vw[i-1][1]
            
            for j in range(V+1):
                if i>0 and j>0:
                    if j >= v_i:
                        dp[i][j] = max(dp[i-1][j], dp[i-1][j-v_i] + w_i)
                    else:
                        dp[i][j] = dp[i-1][j]

        return dp[-1][-1]