01背包

class Solution:
    def knapsack(self , V , n , vw ):
        res=[0 for i in range(V+1)]
        for i in range(1,n+1,1):
            for j in range(V,0,-1):
                if j>=vw[i-1][0]:
                    res[j]=max(res[j],res[j-vw[i-1][0]]+vw[i-1][1])
        result=res[V]
        return result

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
from functools import lru_cache
class Solution:
    def knapsack(self , V , n , vw ):
        # write code here
        @lru_cache(maxsize=4000000)
        def helper(V,n):
            if V == 0:
                return 0
            if V < 0:
                return -vw[n+1][1]
            if n < 0:
                return 0
            if vw == []:
                return 0
            return max(vw[n][1] + helper(V-vw[n][0],n-1), helper(V,n-1))
        return helper(V, n-1)

class Solution:
    def knapsack(self , V , n , vw ):
        # write code here
        '''dp是一个矩阵，行是考虑的物品数，分别是0，1，2； 列是背包的可用空间分别是0，1，2，。。。，10；
        而对应位置的值就是给定条件下可以放的最大重量'''
        dp = [[0 for j in range(V+1)] for i in range(n+1)]
        '''这里给vw的index0插入了一个【0，0】是为了之后代码遍历方便点，这样index0 表示考虑0件物品'''
        vw.insert(0,[0,0])
        '''对每一行进行遍历，注意，行的index就是代表考虑最近的index件物品'''
        for row in range(1,n+1):
            for col in range(V+1):
                if vw[row][0]> col:
                    dp[row][col] = dp[row-1][col]
                else:
                    dp[row][col] = max(dp[row-1][col], dp[row-1][col-vw[row][0]] + vw[row][1])
        return dp[n][V]

逻辑就是B站上面那些背包问题的视频的逻辑，其他人的代码更加高效，但是我这个更能理解。