TopCoder子集和问题求助：最小不可达正整数解法解析

作为动态规划新手，碰到这个问题时感到困惑太正常了——这个解法的背后藏着非常巧妙的数学逻辑，咱们一步步拆解清楚，把你的疑问逐个解决。

一、为什么说最大可能和是100000*20？ #

你说得没错，理论上所有元素的总和确实是能达到的最大和，但解法里提到100000*20，本质是题目隐含的输入约束：TopCoder的这道题大概率限定了每个元素的最大值为100000，数组的长度最多为20，所以所有元素的总和上限就是100000*20=2000000。

用这个固定值来定义DP数组的大小，一是避免每次都计算数组总和的额外操作，二是这个值已经覆盖了所有可能的测试用例范围，代码实现起来更简洁。

二、子集运用的逻辑与背后的数学原理 #

这个问题的核心是：找出不在所有子集和集合中的最小正整数，解法的核心逻辑基于一个非常关键的数学结论，咱们先理解这个结论，再看子集/DP的作用：

关键数学结论 #

假设我们已经处理了数组的前k个元素，当前能表示的连续正整数范围是[1, max_reachable]（也就是说1到max_reachable的所有正整数都能被子集和表示）。当加入第k+1个元素num时：

• 如果num > max_reachable + 1：那max_reachable + 1就是答案！因为已有的所有子集和都≤max_reachable，加上num后得到的和都会≥num>max_reachable+1，中间的max_reachable+1完全无法被补全。
• 如果num ≤ max_reachable + 1：新的可表示范围会扩展到[1, max_reachable + num]。因为原来的[1, max_reachable]可以和num组合出[num, max_reachable + num]，而由于num ≤ max_reachable+1，这两个区间是连续的，合并后就能覆盖到max_reachable + num。

子集/DP的作用 #

动态规划在这里的作用是标记所有能被表示的和，用一个布尔数组dp来记录：

• dp[i] = true：表示和为i可以通过子集求和得到
• dp[i] = false：表示和为i无法被表示

我们通过遍历数组元素，逐步更新这个dp数组，最终从1开始找第一个dp[i]为false的数，就是答案。

三、完整的DP解法解析（以你给出的例子S={2,1,2,7}为例） #

步骤1：预处理数组 #

首先把数组排序为{1,2,2,7}——排序是关键，因为我们需要从小到大处理元素，才能应用上面的数学结论。

步骤2：初始化DP数组 #

创建一个布尔数组dp，大小为2000001（对应之前说的100000*20），初始值全为false，然后设置dp[0] = true（空子集的和为0，这是所有子集和的基础）。

步骤3：遍历元素更新DP数组 #

我们同时维护一个max_reachable变量，记录当前能表示的最大连续正整数，初始为0。

1. 处理第一个元素1：
   • 因为1 ≤ max_reachable + 1 = 0+1=1，所以更新max_reachable = 0+1=1
   • 遍历从1到max_reachable，设置dp[1] = true
2. 处理第二个元素2：
   • 2 ≤ 1+1=2，更新max_reachable =1+2=3
   • 倒着遍历从3到2：
     • dp[3] = dp[3-2] = dp[1] = true
     • dp[2] = dp[2-2] = dp[0] = true
3. 处理第三个元素2：
   • 2 ≤3+1=4，更新max_reachable=3+2=5
   • 倒着遍历从5到2：
     • dp[5] = dp[5-2] = dp[3] = true
     • dp[4] = dp[4-2] = dp[2] = true
4. 处理第四个元素7：
   • 7 >5+1=6，直接确定答案是6，不需要继续更新DP数组

为什么要倒着遍历？ #

倒着遍历是为了避免重复使用同一个元素多次。如果正着遍历，比如处理2的时候从2到5，那么当我们设置dp[2]=true后，后续遍历到4时，会用dp[4-2]=dp[2]（刚设置的true），这就相当于重复使用了两次2，不符合子集“每个元素最多用一次”的要求。倒着遍历则可以保证每个元素只被用一次。

四、最终代码思路（伪代码） #

def findSmallestUnrepresentable(S):
    S.sort()
    max_possible = 100000 * 20
    dp = [False] * (max_possible + 1)
    dp[0] = True
    max_reachable = 0
    
    for num in S:
        if num > max_reachable + 1:
            break
        # 倒着更新dp数组
        for i in range(max_reachable + num, num -1, -1):
            if dp[i - num]:
                dp[i] = True
        max_reachable += num
    
    # 找第一个无法表示的正整数
    for x in range(1, max_possible +1):
        if not dp[x]:
            return x
    # 如果所有数都能表示，返回max_reachable+1
    return max_reachable +1

内容的提问来源于stack exchange，提问作者nishant_boro