算法练习 Leetcode 力扣 416. Partition Equal Subset Sum 使用0-1背包问题 2维dp模版的 Python 解法

feellikelearning December 12, 2020 0 Comments

问题描述

这题的最优解是使用Bottom up DP, 题目描述和详细解法可以参考这篇文章. 本文示范一下这题也可以直接使用这篇文章总结的0-1背包问题2维dp模版一字不改直接解

0-1背包问题2维度dp模版解法

问题稍微转换一下就可以等价成为0-1背包问题:
如果nums的和为奇数, 直接返回False, 因为不可能分成等和的两半加起来还是奇数.
有N个物品, 每个物品Cost为nums[i], Value为nums[i], 其中 i 属于 [0, …, N-1]
有一个书包, 容量为sum(nums) / 2
求书包能装下的最大Value 是否就是sum(nums) / 2

Python 2 代码实现如下

class Solution(object):
    def maxKnapsackValue(self, N, C, W, V):
        # init dp
        row = [0] * (1 + V)
        dp = []
        for i in range(N + 1):
            dp.append(list(row))

        for i in range(1, N + 1):
            for v in range(1, V + 1):
                dp[i][v] = dp[i - 1][v]
                if v - C[i - 1] >= 0:
                    dp[i][v] = max(
                        dp[i][v], 
                        dp[i - 1][v - C[i - 1]] + W[i - 1]
                    )
        return dp[N][V]

    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        isum = sum(nums)
        if isum % 2 != 0:
            return False
        target = isum / 2
        print target
        
        n = len(nums)
        return self.maxKnapsackValue(
            n, nums, nums, target) == target

该解法能过OJ, 虽然时间和空间用的都比较多.