元组最优分组算法求解：TRPG骰子机制概率计算需求

核心目标拆解 #

最终成功数 = 成功组数量 - 负和组数量。设总组数为X，非负非成功组数量为Z，则：
最终成功数 = 2*成功组数量 + Z - X
我们的目标转化为：尽可能多的组是成功组（和≥Y）或非负非成功组（和≥0且<Y），最小化负和组数量。

分步策略与算法 #

1. 预处理：排序元组 #

先将元组按降序排序，优先利用大正数凑成功组，节省元素资源。

2. 贪心凑成功组 #

从最大的元素开始累加，直到累加和≥Y，形成一个成功组。移除这些元素，成功组计数S加1。重复此过程：

• 单个元素≥Y时，直接单独成组（最划算，节省其他元素）。
• 需多个元素累加时，优先用最少元素凑出≥Y的和（比如大正数+小正数）。
• 停止条件：剩余元素数量 ≤ (X - S)（需保证剩余元素能分成X-S组，每组至少1个），或无法再凑出≥Y的和。

3. 剩余元素分组（凑非负组，减少负和） #

设剩余元素需分成K = X - S组，每组至少1个元素：

• 剩余元素再次降序排序。
• 先给每个组分配一个最大的元素（保证每组有一个较大的数，避免被负数拉成负和）。
• 把剩下的元素依次加到当前和最小的组中，尽量维持组和非负。
• 若剩余元素全是负数，只能尽量降低负和绝对值，负和组数量即为K。

4. 微调优化（可选） #

尝试拆分一个成功组，看能否用拆分出的元素多凑出成功组+非负组，提升最终成功数。比如：一个成功组由A+B组成（A≥Y-B），拆分后A单独成成功组，B和其他元素凑成非负组，S不变但Z增加，最终成功数提升。

代码实现（Python） #

def optimal_grouping(numbers, X, Y):
    numbers = sorted(numbers, reverse=True)
    remaining = numbers.copy()
    success_groups = []
    # 第一步：凑成功组
    while len(remaining) > (X - len(success_groups)):
        current_sum = 0
        current_group = []
        for idx, num in enumerate(remaining):
            current_sum += num
            current_group.append(num)
            if current_sum >= Y:
                success_groups.append(current_group)
                remaining = remaining[:idx] + remaining[idx+1:]
                break
        else:
            # 无法再凑出成功组，终止循环
            break
    
    K = X - len(success_groups)
    negative_groups = 0
    # 第二步：分配剩余元素到K个组
    groups = [[num] for num in remaining[:K]]
    remaining = remaining[K:]
    # 将剩余元素加到当前和最小的组
    for num in remaining:
        min_sum_idx = min(range(K), key=lambda i: sum(groups[i]))
        groups[min_sum_idx].append(num)
    
    # 统计负和组数量
    negative_groups = sum(1 for g in groups if sum(g) < 0)
    final_success = len(success_groups) - negative_groups
    return final_success, success_groups, groups

代码说明 #

• 输入：numbers为整数元组，X为分组数，Y为成功组阈值。
• 输出：最终成功数、成功组列表、剩余组列表。
• 适配TRPG概率测试：可循环调用该函数，传入随机生成的骰子结果元组，统计多次测试的成功概率分布。

示例验证 #

以题目示例：X=3，Y=5，元组[6,5,-2]

1. 排序后为[6,5,-2]
2. 6、5分别单独成成功组，剩余[-2]需分1组
3. 负和组数量为1，最终成功数=2-1=1，符合题目描述。

调用代码：optimal_grouping([6,5,-2], 3,5)，返回最终成功数1，结果正确。

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