前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【DP、Greedy】416. Partition Equal Subset Sum

【DP、Greedy】416. Partition Equal Subset Sum

作者头像
echobingo
发布2019-06-11 16:59:02
4800
发布2019-06-11 16:59:02
举报
文章被收录于专栏:Bingo的深度学习杂货店
问题描述:

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

  • Each of the array element will not exceed 100.
  • The array size will not exceed 200.
Example 1:
代码语言:javascript
复制
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
代码语言:javascript
复制
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
解题思路:

划分成相等的子集和,容易得到以下性质:

  • 如果只有一个数,则肯定不能划分;
  • 如果所有数和为奇数,则肯定不能划分;
  • 划分的目标是所有数总和除以2。
方法1:使用贪心算法求解:
  • 先对所有数进行从大到小排序
  • 使用双指针 i,j;i 指向当前数字,j 向后移动;
  • 双循环,外层循环 i 每次指向一个数字,内层循环 j 在移动的过程中: 1、如果当前累加和 < 目标,则更新累加和; 2、如果累积和 == 目标,则返回 True; 3、如果累加和 > 目标,则什么都不做。
  • 最后,如果不能划分,返回 False。

例如:nums = 10,8,7,6,5,4,第一次循环,i 指向 10,j 在遍历的过程中,10 和 8 可以装进去,但是后面的数字不行;第二次循环,i 指向 8,j 在遍历的过程中,8、7 和 5 可以装进去,并且正好等于 20,则返回 True。

注意: 必须从大到小排序,因为我们使用的是一种贪心的策略:每次先装大的,再装次大的。如果次大的装入超过了目标,则会继续向后挑选第三大、第四大...,这样是可行的。但是,如果不排序,如 nums = 4,5,6,7,8,10,采取上述方法会返回 False。

时间复杂度为 O(n^2),空间复杂度为 O(1)。

Python3 实现如下:
代码语言:javascript
复制
class Solution:
    def canPartition(self, nums):
        lens = len(nums)
        if lens == 1:
            return False
        tot = sum(nums)
        if tot % 2 == 1:
            return False
        target = tot // 2
        nums.sort(reverse=True)  # 从大到小排序
        for i in range(lens):
            tem = 0
            for j in range(i, lens):
                if tem + nums[j] == target:
                    return True
                elif tem + nums[j] < target:
                    tem += nums[j]
        return False

print(Solution().canPartition([6,5,4,8,10,7]))  # True
方法2:使用动态规划求解:

实际上,这道题是01-背包问题的应用:01-背包问题及其应用

我们可以将问题转化为以下的形式:是否有一个子数组的元素之和,恰好等于原数组元素之和的一半呢?而对于原数组中的每一个元素,都有两种状态:在子数组里面或者不在子数组里面(先假设存在这个子数组)。这样一看,我们就能发现这个问题与0-1背包问题非常相似,因此我们可以采用0-1背包问题的解法去解决这道问题。

在这道题目中,原数组里面的每个元素都可以看作是一种物品,而这件物品的重量和价值都为元素值;原数组的和的一半可看作背包的最大承重量,而当背包能放下物品的最大价值为原数组和的一半时,就返回真,否则返回假。

因此,我们就能很容易的得到以下算法:

  • 在这个问题中,背包容量为数组和的一半,因此需要 dp[len(nums)+1][sum(nums)//2+1] 大小的数组,其中 dp[i][j] 表示前 i 个数放入容量为 j 的背包中的目标值;
  • 如果 j 小于当前第 i 个数的容量,即 j < numsi-1,则 dp[i][j] = dp[i-1][j]
  • 否则,dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1]] + nums[i-1])
  • 在每填完表的一行时,就应该判断一下是否达到了目标值,即 dp[i][j] 是否为 True,而不是等更新完表的所有行再判断;
  • 如果更新完所有行,dp[-1][-1] 不等于目标值,则说明不能划分,返回 False。

时间复杂度为 O(n^2),空间复杂度为 O(n*(sum(nums) // 2))。

Python3 实现:
代码语言:javascript
复制
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        lens = len(nums)
        if lens == 1:
            return False
        tot = sum(nums)
        if tot % 2 == 1:
            return False
        tar = tot // 2
        dp = [[0] * (tar+1) for _ in range(lens+1)]
        for i in range(1, lens + 1):
            for j in range(1, tar + 1):
                if j < nums[i-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1]] + nums[i-1])
            if dp[i][j] == tar:  # 更新完一行就应该判断一下
                return True
        return False

print(Solution().canPartition([2,5,3,4]))  # True
print(Solution().canPartition([5,1,3,5]))  # False

注:这类题目,即物品(数组元素)有存在与否两种状态的题目,都可以用01-背包的思想和解法进行解决。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019.06.05 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题描述:
    • Example 1:
      • Example 2:
      • 解题思路:
        • 方法1:使用贪心算法求解:
          • Python3 实现如下:
            • 方法2:使用动态规划求解:
              • Python3 实现:
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档