带容量限制的m个箱子分配n个相同小球的组合数计算及通用算法

问题明确 #

给定n个完全相同的小球，m个互不相同的箱子，第i个箱子的最大容量为c_i（所有c_i≤15），求所有满足以下条件的分配方案数：

• 每个箱子放入的小球数为非负整数
• 单个箱子的小球数不超过其容量上限
• 所有箱子的小球数总和恰好为n

传统方法的局限性 #

你提到的星与条、容斥原理本身是正确的，但适用场景有限：

• 基础星与条仅能处理无容量上限的分配问题
• 容斥原理可以处理带上限的场景，但时间复杂度为O(2^m)，当箱子数量m超过20时计算量会指数级爆炸，确实不具备普适性

通用迭代动态规划解法（无递归深度问题） #

该方法完全采用迭代实现，不存在递归深度超限的问题，即使n达到10^4级别也可以正常运行，且因为箱子容量最高只有15，可通过前缀和进一步优化计算效率。

核心思路 #

我们逐一枚举每个箱子，维护当前状态下放入j个小球的合法方案数：

• 状态定义：dp[j] 表示当前已处理的所有箱子中，恰好放入j个小球的分配方案总数
• 初始状态：没有处理任何箱子时，只有放入0个小球这1种合法方案，即dp[0]=1，其余dp[j>0]=0
• 状态转移：每加入一个容量为c的新箱子，新的方案数等于之前所有放入k个球（k的范围是max(0, j-c) ≤k ≤j）的方案数之和，对应新箱子放入j-k个球（不超过容量c）

优化点 #

1. 滚动数组优化：仅用一维数组存储状态，空间复杂度为O(n)
2. 前缀和优化：将每次转移的求和操作复杂度从O(c)降到O(1)，整体时间复杂度为O(m*n)
3. 边界剪枝：如果n超过所有箱子的总容量sum(capacities)，直接返回0，无需额外计算

可直接运行的Python实现 #

def count_valid_distributions(target_balls: int, box_capacities: list[int]) -> int:
    total_capacity = sum(box_capacities)
    # 总容量不足或目标球数为负，直接返回0
    if target_balls > total_capacity or target_balls < 0:
        return 0
    # 初始化dp数组
    dp = [0] * (target_balls + 1)
    dp[0] = 1
    for cap in box_capacities:
        # 计算前缀和加速转移
        prefix = [0] * (target_balls + 1)
        prefix[0] = dp[0]
        for idx in range(1, target_balls + 1):
            prefix[idx] = prefix[idx - 1] + dp[idx]
        # 计算新的dp状态
        new_dp = [0] * (target_balls + 1)
        for j in range(target_balls + 1):
            left_bound = max(0, j - cap)
            if left_bound == 0:
                new_dp[j] = prefix[j]
            else:
                new_dp[j] = prefix[j] - prefix[left_bound - 1]
        dp = new_dp
    return dp[target_balls]

大n场景适配 #

因为所有箱子的容量都不超过15，总容量最多为15*m，若输入的n远大于该值，会直接触发边界剪枝返回0，不存在n过大无法计算的问题。如果需要对大n做排序/反排序操作，也可以基于生成函数展开的结果直接计算组合数，无需遍历所有n的取值。

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