416分割等和子集

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # 如果用回溯算法 全排列或者全组合，会是 2**n 复杂度超时,所以用动态规划的 0-1 背包解法;
        # 将 题目 抽象为一个 只取一次的0-1背包问题(注定了后边的背包遍历顺序是倒叙)；
        # 从nums 内 取n个数，使这n个数 的和 = 装满假定的背包容量 sum(nums)/2 
        # 抽象重量为 nums的元素； 抽象价值为 nums的元素；重量和价值共用一套值;
        # 定义 d[j] 为 背包容量为 j 时，最大的背包价值;
        # d[j] = max(d[j],d[j-weight(i)]+value(i)) max(无i，有i)
        # 初始化
        target = sum(nums)/2
        d = [ 0 for _ in range(int(target+2))]
        print(target)
        for i in range(len(nums)):                  # 0-1背包先遍历 物品;
            for j in range(int(target+1),nums[i]-1,-1):    # 只取一次的 0-1背包 ，背包只能倒叙，可以打印d数组看出原因;
                d[j] = max( d[j], d[j-nums[i]]+nums[i] )
        # print(d)        # 打印 d 检查。
        for _ in d:
            if _==target:
                return True 
        return False