Sep.23 0-1背包问题

两只队伍分物资

这里有一堆物资待分配，物资总数量不超过200 ( 0 < m ≤ 200 ) (0 请问是否可以将这堆物资分配给两个队伍，使得两个队伍的全部的物资重量和相等。

示例1

• 输入
  [1, 5, 11, 5]
• 输出
  true

—说明
数组可以分为 [1, 5, 5] 和 [11]

示例2

• 输入
  [1, 2, 3, 5]
• 输出
  false

# python3
class Solution:
    def canPartition(self , nums):
        # write code here
        if nums == []:
            return True
        if sum(nums) % 2 == 1:
            return False
        target = int(sum(nums) / 2)
        dp = [True] + [False] * target
        for i, num in enumerate(nums):
            for j in range(target, num - 1, -1):
                dp[j] |= dp[j - num]
        return dp[target]

购物车问题
题解：购物车