python集合划分问题（Partition Problem）

### Python 集合划分问题的算法实现

集合划分问题是组合优化中的经典难题之一，属于NP难问题。该问题的目标是在给定一组正整数的情况下，判断这些数字能否被划分为两个子集，使得这两个子集的元素之和相等。

#### 动态规划解决方案

动态规划是一种有效的解决方法，能够处理较小规模的数据输入。通过构建一个二维布尔数组 `dp` 来记录可能的状态转移情况：

- 行表示当前考虑的物品数量
- 列代表目标容量（即总和的一半）

对于每一个元素，有两种选择：要么放入背包，要么不放。最终目的是找到是否存在一种方式让背包装满恰好一半的总量。

def can_partition(nums):
    total_sum = sum(nums)
    
    # 如果总数不是偶数，则不可能平分
    if total_sum % 2 != 0:
        return False
    
    target = total_sum // 2
    n = len(nums)

    dp = [[False] * (target + 1) for _ in range(n + 1)]
    
    # 初始化边界条件
    for i in range(n + 1):
        dp[i][0] = True
        
    for i in range(1, n + 1):
        for j in range(1, target + 1):
            if nums[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
                
    return dp[n][target]

# 测试案例
nums = [1, 5, 11, 5]
print(can_partition(nums))  # 输出应为True

此代码实现了基于动态规划的方法来检测是否能将列表分成两部分使它们各自加起来相同[^1]。