代码随想录算法训练营第四十二天| 01背包问题、416.分割等和子集

代码随想录算法训练营第四十二天| 01背包问题、416.分割等和子集

题目

https://www.acwing.com/problem/content/2/

2.01背包问题

if __name__ == '__main__':
    N, V = input().split(' ')
    N = int(N)
    V = int(V)
    v = [0] * (N + 1)
    w = [0] * (N + 1)
    dp = [[0] * (V+1) for _ in range(N)]
    for i in range(N):
        v[i], w[i] = input().split(' ')
        v[i] = int(v[i])
        w[i] = int(w[i])
    # 初始化
    for j in range(v[0], V + 1):
            dp[0][j] = w[0]
    # 物品个数遍历
    for i in range(1, N):
        # 遍历背包容量
        for j in range(V+1):
            if j < v[i]:
                dp[i][j] = dp[i - 1][j]
            else:
                # 放i物品和不放i物品
                dp[i][j] = max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])
    print(dp[N-1][V])

if __name__ == '__main__':
  # 滚动数组
    N, V = input().split(' ')
    N = int(N)
    V = int(V)
    v = [0] * (N + 1)
    w = [0] * (N + 1)
    dp = [0] * (V + 1)
    for i in range(N):
        v[i], w[i] = input().split(' ')
        v[i] = int(v[i])
        w[i] = int(w[i])
    for i in range(N):
        for j in range(V, v[i] - 1, -1):
            dp[j] = max(dp[j - v[i]] + w[i], dp[j])
    print(dp[V])

题目

416.分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

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