如何将n个相同球分配到k个不同容量相同盒子？附实例求解

嘿，咱们来一步步解决这两个问题，先从第一个通用问题说起～

首先得把问题的核心要素拎清楚：

• 球是相同的：只需要关注每个盒子里的球数，不用管具体是哪些球
• 盒子是相同的：分配顺序不算不同方法，比如（3,2）和（2,3）算同一种
• 盒子容量各不相同：每个盒子有最大容纳量，而且这些最大值不一样

这种问题本质是带限制条件的整数分拆问题，因为盒子相同，我们可以先把容量按从大到小排序（比如c₁≥c₂≥…≥cₖ），这样只需要找满足以下条件的非递增整数组(x₁,x₂,…,xₖ)：

• x₁ + x₂ + … + xₖ = n
• 0 ≤ xᵢ ≤ cᵢ（每个盒子的球数不超过自身容量）
• x₁ ≥ x₂ ≥ … ≥ xₖ（因为盒子相同，用降序唯一表示一种分配方式）

没有通用的公式能直接计算，常用的解决方式有两种：

• 枚举递归法：从容量最大的盒子开始，枚举它可能放的球数（范围是min(c₁, n)到不小于下一个盒子的球数），然后递归处理剩下的球和剩下的盒子，直到所有球分配完或者盒子用完。
• 动态规划法：定义dp[i][j]表示用前i个已排序的盒子分配j个球的方法数，状态转移时要保证第i个盒子的球数不超过cᵢ，且不大于前一个盒子的球数（维持非递增），逐步填充dp表得到结果。

首先，因为盒子相同，我们先把容量按降序排：10,5,2,1。现在要找所有非递增的整数组(x₁,x₂,x₃,x₄)，满足：

• x₁+x₂+x₃+x₄=16
• 10≥x₁≥x₂≥x₃≥x₄≥0
• x₂≤5，x₃≤2，x₄≤1

咱们逐个枚举可能的x₁值：

情况1：x₁=10（最大容量） #

剩下的球数：16-10=6，需要分给容量5、2、1的盒子，且x₂≥x₃≥x₄，x₂≤5。

• x₂=5：剩下6-5=1，x₃+x₄=1 → 只有(1,0)，组合：(10,5,1,0)
• x₂=4：剩下6-4=2，x₃+x₄=2 → 可行组合：(2,0)、(1,1)，对应(10,4,2,0)、(10,4,1,1)
• x₂=3：剩下6-3=3，x₃+x₄=3 → 只有(2,1)，组合：(10,3,2,1)
• x₂≤2时，x₃+x₄最多2+1=3，无法凑够剩下的球数，停止。
  此情况共4种方法。

情况2：x₁=9 #

剩下的球数：16-9=7，分给容量5、2、1的盒子，x₂≤5。

• x₂=5：剩下7-5=2，x₃+x₄=2 → 可行组合：(2,0)、(1,1)，对应(9,5,2,0)、(9,5,1,1)
• x₂=4：剩下7-4=3，x₃+x₄=3 → 只有(2,1)，组合：(9,4,2,1)
• x₂≤3时，x₃+x₄最多3，无法凑够剩下的4个球，停止。
  此情况共3种方法。

情况3：x₁=8 #

剩下的球数：16-8=8，分给容量5、2、1的盒子，x₂≤5。

• x₂=5：剩下8-5=3，x₃+x₄=3 → 只有(2,1)，组合：(8,5,2,1)
• x₂≤4时，x₃+x₄最多3，无法凑够剩下的4个球，停止。
  此情况共1种方法。

情况4：x₁≤7 #

剩下的球数≥16-7=9，但剩下3个盒子的最大总容量是5+2+1=8，无法凑够9个球，所以没有可行方法。

把所有情况加起来，总共有4+3+1=8种分配方式。

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