题解 | #dp# #01背包#

#coding:utf-8
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算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
        max_vol = 0
        dp = [[0 for i in range(0, V + 1)] for i in range(0, n + 1)]
        print ("dp shape: ", len(dp), len(dp[0]))
        #init
        #dp[i][j] 代表第i个物品当前最大能装的重量

        #process
        for i in range(1, n + 1):
            cur_w = vw[i - 1][0]
            for j in range(1, V + 1):
                if cur_w > j:
                    dp[i][j] = dp[i - 1][j]
                else:
                    #比较不拾取第i- 1个item和拾取的价值大小
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1])

        return dp[n][V]