代码随想训练营第四十二天（Python）｜ 0-1 背包基础、416. 分割等和子集

[背包基础]
题目:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
1、二维方式解决背包问题

class Solution:

    def solve_bag(self, weight, value, bag_weight):
        #  dp[i][j] 代表物品为 i,背包重量为 j 的最大价值
        dp = [[0]*(bag_weight+1) for _ in range(len(value))]

        # 初始化数组
        for j in range(weight[0], bag_weight + 1):
            dp[0][j] = value[0]

        # 遍历
        for i in range(1, len(value)):  # 先遍历物品
            for j in range(bag_weight + 1):  # 遍历背包容量
                # 递推公式
                if j < weight[i]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])
        return dp[len(value) - 1][bag_weight]

2、一维方式解决背包问题
注意点:倒序遍历，保证物品 i 只被放入一次
dp[j] 代表背包容量为 j 的背包的价值总量为 dp[j]。

class Solution:

    def solve_bag(self, weight, value, bag_weight):
        #  dp[j] 代表背包重量为 j 的最大价值
        dp = [0] * (bag_weight + 1)

        # 初始化数组
        dp[0] = 0

        # 遍历
        for i in range(len(value)):  # 先遍历物品
            for j in range(bag_weight, weight[i] - 1, -1):  # 遍历背包容量
                # 递推公式
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

        return dp[bag_weight]

416. 分割等和子集

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2 != 0:
            return False
        target = sum(nums) // 2
        dp = [0] * (target+1)
        for num in nums:
            for j in range(target, num-1, -1):
                dp[j] = max(dp[j], dp[j - num] + num)
        return dp[target] == target