当前位置:   article > 正文

@[TOC](python数据结构与算法练习-动态规划问题)_python 给你一个只包含正整数的非空数组

python 给你一个只包含正整数的非空数组

分割等和子集(背包变形)

来源

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

示例 1:

输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5][11]
  • 1
  • 2
  • 3

示例 2:

输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。
  • 1
  • 2
  • 3

思路:

思路:这里说为什么可以划分为问题:
1)0-1背包问题是说往背包放入商品使得背包内物品价值最大,而这里是找到数组使数组的和等于总集合和的一半。
2)同样是从给定列表里面取元素取的元素等于一个值,一个是最大值一个是给定值,所以后者相当于把背包容量定义为了集合总和的一半,那么当放入的元素和等于背包容量也就是说找到了一个子集,那么剩下的子集和也必定是背包容量的一半。
注意物品的价值在这里就是物品本身而已,最后只要判断dp右下角元素的值是否和背包容量是不是相同即可。

python实现

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sums = int((sum(nums))/2)
        #集合和为奇数时显然是不可以的
        if sum(nums) % 2 != 0:
            return False
        else:
        # 创建背包
            dp =  [[0 for j in range(sums+1)] for i in range(len(nums))]
            #初始化背包
            for i in range(len(nums)):
                dp[i][0] = 0
            for j in range(nums[0],sums+1):
                dp[0][j] = nums[0]


            for i in range(1,len(nums)):
                for j in range(sums+1):
                    if j < nums[i]:
                        dp[i][j] = dp[i-1][j]
                    else:
                        dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i])
            return dp[len(nums) - 1][sums] == sums
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

这里仅供自己复习使用,也欢迎批评指正。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/744928
推荐阅读
相关标签
  

闽ICP备14008679号