python - 给定n个球和m个箱子，每个箱子有一定容量，有多少种组合？

Question

给定 n 个相同的球和 m 个不同的箱子，每个箱子都有一定的容量（从 0 到 z，其中 z 是小于或等于 15 的非负整数），有多少种不同的方式来分配球？是否有解决此类问题的通用算法？

我遇到了“星条”和“包含/排除”原则，但我也在 stackoverflow 上找到了一些问题/答案，但没有一个答案似乎足够通用，可以扩展到任意大小的 n。似乎解决它的一种方法是使用动态编程。对于任意 n，如何做到这一点（以下解决方案的问题是 Python 中的递归深度对于相对较小的 n 变得太大，例如 n = 1000）。

rank 和 unrank 组合将 k 个球分配到 n 个不同容量的 bin 中

我没有正确理解这一点吗？有人可以像向五岁的孩子那样向我解释吗？

标签： pythonalgorithmdynamic-programming

Answer 1

这个问题可以通过生成函数来建模，其中每个 bin 产生一个多项式 (1 + z + z ² + ... + z ^c )，其中 c 是 bin 的容量，我们取 bin 多项式的乘积并提取系数的 z ⁿ。

直接的非递归动态规划算法是从左到右评估乘积。如果需要，您可以花哨并混合和匹配您的乘法算法，尤其是在 c ≤ 15 的情况下。