01背包

class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # dp[i][j]代表容量为j时在第i个物品能装的最大重量
        # 状态转移方程
        # 两种情况：
        # 1）当前物品的体积超过j,那么无法放入该物品，dp[i][j] = dp[i-1][j]
        # 2）当前物品的体积不超过j,有两种选择，取两者的较大值：
        #     不放该物品，能装的最大重量为dp[i-1][j]
        #     放入该物品，能装的最大重量为dp[i-1][j-cur_v] + cur_w
        # 观察数组可知，当体积为0或物品为0时，最大重量为0，因此第0行和第0列为0
        # 初始化二维数组
        dp = [[0]*(V+1) for i in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, V+1):
                # 当前物品的体积
                cur_v = vw[i-1][0]
                # 当前物品的重量
                cur_w = vw[i-1][1]
                if cur_v > j:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-cur_v] + cur_w)
        return dp[-1][-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: int, n: int, vw: List[List[int]]) -> int:
        # V 体积 。 n :物品个数 
        # 就是填表的过程。然后就出来结果了。
        # 列 是 体积的大小 
        # 行 是 物品的个数 + 1
        # 第一行 第一列 都是 0 。
        # 第 dp[row][col] 代表：在 可以装 col 的情况下，选择 前row个物品的最优解。
        # dp = [[0] * (V + 1)] * (n+1)  我这个dp数组生成的有问题,, 我。。我服了啊。用下面的就可以。打印出来长一模一样啊。
        dp = [[0 for i in range(V+1)] for j in range(n+1)]
        for row in range(1, n+1): 
            # 从左到右填表
            for col in range(1, V + 1):
                # 从上到下填表 
                # 到第row 个的时候咋选择
                # 首先看当前物品的重量是否超过当前体积。如果超过了。就填正上面的解。
                if vw[row-1][0] > col:
                    # col 是当前体积。 vw[row-1][0] 是代表到第row-1个物品。
                    # 说明不能装当前物品。当前局部最优解就是 dp[row-1][cow].
                    dp[row][col] = dp[row-1][col]
                else:
                    # 当前物品的重量小于当前的体积
                    # 这个时候有俩种情况，装当前的物品还是不装当前的物品
                    # 然后比较俩种情况，谁好选择谁

                    # 第一种情况：装当前物品，那么剩余的体积就是 col - 当前体重。
                    data_rest = col - vw[row-1][0] # 需要计算在data_rest体重的情况下，前 row-1个的最优解
                    data_1  = vw[row-1][1] + dp[row-1][data_rest]

                    # 第二种情况：不装当前物品
                    data_2  = dp[row-1][col] # 就正上方的数据

                    # 比较data_1 data_2 
                    dp[row][col] = max(data_1, data_2)
        
        return dp[-1][-1]

为啥生成dp数组打印出来一模一样，一个可以，一个不行。服了。。