具有 k-chocolates-once 约束的巧克力分配问题

Question

问题：将 N 块巧克力分发给 3 个孩子，以便任何孩子一次最多可以吃到 k 块巧克力。巧克力可以通过多少种方式分发？ 例如：

输入：

k = 2
n = 2

输出：

maximum number of ways: 6

解释：

{[2, 0, 0], [0, 2, 0], [0, 0, 2], [1, 1, 0], [0, 1, 1], [1, 0, 1]}

输入

k = 5 
n = 15

输出：

maximum number of ways: 1

解释：

{[5, 5, 5]}

首先，我尝试通过使用排列和组合制定方程式来获得直接答案。我在考试中遇到了这个问题，我制定了一个公式，我不太记得了，但它有点像这样：

for i in range(3+1):
  total += (-1)**(i)*comb(3, 1)*comb(n-i*(k+1)+2, 2)

这是我记得的，但是错了。

Answer 1

比如说，我们要给第一个孩子

0 <= i <= k

巧克力。然后，我们的问题就变得容易了一些，将

M = N-i

巧克力分给两个孩子。

由于另一个孩子不能拥有超过

k

，因此第一个孩子可以拥有

max(0, M-k)

和

min(M, k)

之间的任意位置。因此，在两个孩子之间分配

M

巧克力的方法有

max(min(M, k)-max(0, M-k)+1, 0)

。

现在在 3 路分配中，我们考虑给第一个孩子

0..k

巧克力，然后总结分配其余孩子的方法：

# yes, that's the whole solution
sum(max(min(M, k)-max(0, M-k)+1, 0) for M in range(n-k, n+1))