算法練習 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, 雖然時間和空間用的都比較多.