整数列表分配至双容量限制列表：寻求动态规划解决方案

问题明确 #

给定整数列表，需将每个整数分配到两个列表A、B中的一个，要求A的总和 < 容量C且B的总和 < 容量C。贪心算法在部分边缘场景下无法找到可行解，因此需要动态规划方案。

核心思路转化 #

问题等价于：寻找原列表的一个子集S，使得：

• sum(S) < C（列表A的总和）
• sum(原列表) - sum(S) < C（列表B的总和）

推导可得子集S的总和需满足：sum_total - C < sum(S) < C（其中sum_total为原列表总和）。只要找到符合该范围的子集S，即可完成分配。

动态规划实现步骤 #

1. 前置判断（快速排除无解情况） #

• 若存在任意整数 ≥ C：无法分配（该数放入任一列表都会导致总和不低于C）。
• 若sum_total ≥ 2*C：无法分配（两个列表总和都< C的话，总和加起来<2C，与sum_total≥2C矛盾）。

2. DP状态定义与转移 #

使用一维DP数组优化空间：

• dp[j]：表示能否从已遍历元素中选出总和为j的子集。
• 状态转移：对于当前元素num，倒序遍历j从capacity-1到num，若dp[j-num]为True，则设置dp[j] = True（倒序避免重复使用同一元素）。
• 用prev数组记录选择路径，方便后续回溯得到具体分配列表。

3. 寻找可行子集并回溯 #

遍历符合范围[max(0, sum_total - C + 1), capacity-1]的j，找到第一个dp[j]为True的目标总和，再通过prev数组回溯确定每个元素是否属于子集S（列表A），剩余元素则属于列表B。

代码实现 #

def split_into_two_lists(nums, capacity):
    sum_total = sum(nums)
    # 快速排除无解场景
    if any(num >= capacity for num in nums):
        return None
    if sum_total >= 2 * capacity:
        return None
    
    max_target = capacity - 1
    min_target = sum_total - (capacity - 1)
    min_target = max(min_target, 0)
    
    # 一维DP数组，记录是否能凑出对应总和
    dp = [False] * (max_target + 1)
    dp[0] = True
    # prev[i][j]标记第i个元素是否被选中以凑出总和j
    prev = [[False]*(max_target +1) for _ in range(len(nums))]
    
    for i in range(len(nums)):
        num = nums[i]
        # 倒序遍历，防止重复使用当前元素
        for j in range(max_target, num - 1, -1):
            if dp[j - num]:
                dp[j] = True
                prev[i][j] = True
    
    # 找到符合条件的目标总和
    target_j = None
    for j in range(min_target, max_target + 1):
        if dp[j]:
            target_j = j
            break
    if not target_j:
        return None
    
    # 回溯分配元素
    list_a, list_b = [], []
    current_j = target_j
    for i in range(len(nums)-1, -1, -1):
        num = nums[i]
        if prev[i][current_j]:
            list_a.append(num)
            current_j -= num
        else:
            list_b.append(num)
    
    return list_a, list_b

# 测试案例：贪心可能出错的场景
nums = [9, 8, 7]
capacity = 16
result = split_into_two_lists(nums, capacity)
if result:
    a, b = result
    print(f"列表A: {a}，总和: {sum(a)} < {capacity}")
    print(f"列表B: {b}，总和: {sum(b)} < {capacity}")
else:
    print("无法分配")

边缘场景处理 #

• 单个元素接近容量：比如元素为C-1，DP会优先将其单独放入一个列表，避免与其他元素叠加超容。
• 总和接近2C：比如sum_total=2C-1，此时必然有一个列表总和≥C，DP会找不到符合条件的子集，返回None，符合实际情况。
• 多个小元素叠加风险：比如多个元素总和刚好等于C，DP会自动规避将这些元素放入同一列表的情况。

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