使用动态规划算法将球分配到“给定容量的箱子”中

Question

我想知道怎样使用DP解决这个问题。

给定n个球和m个箱子，每个箱子都有最大容量c1、c2、...cm。将这些n个球分配到这些m个箱子中的总方式数是多少？

我面临的问题是：

1. 如何找到递归关系（当容量都是单个常数c时，我可以）。 2. 将会有几个测试用例，每个测试用例都有自己的c1，c2....cm组合。所以，DP实际上如何应用于所有这些测试用例，因为答案明确取决于现在的c1，c2....cm，而我不能存储（或预先计算）所有c1，c2....cm的组合的答案。 此外，我也想不出为这个问题提供任何直接的组合公式，我也不认为有这样的公式存在。

- Andrew

---

投票以将其移至math.stackexchange.com。 - Dan W

Answer 1

您可以定义函数，假设限制c [0]，c [1]，... c [m-1]为固定值，然后编写递归公式，返回将n个球分配到从索引k开始的箱子中的方法数。采用这种方法，基本公式如下：

def solutions(n, k):
    if n == 0:
        return 1  # Out of balls, there's only one solution (0, 0, 0, 0 ... 0)
    if k == m:
        return 0  # Out of bins... no solutions
    total = 0
    for h in xrange(0, min(n, c[k])+1): # from 0 to c[k] (included) into bin k
        total += solutions(n - h, k + 1)
    return total

那么你需要添加记忆化（这将等同于DP方法）和其他优化，例如如果n>c[k]+c[k+1]+c[k+2]+...，那么你知道没有解决方案需要搜索（并且可以预先计算部分和）。

- 6502

---

好的，似乎两个测试集之间不能有任何关系，例如{n,m和c1,c2,....cm}和{x,y和c1,c2,....cy}。但是对于给定的测试集，仍然有足够的动态规划空间。 - Andrew

Answer 2

1. 这个问题存在一个组合公式。找到解决方案的问题等同于找到以下方程的解的数量
   x1 + x2 + x3 + ... + xm = n
其中 xi < ci
这相当于在以下方程中找到 x^n 的系数
(1+x+..x^c1)(1+x+..+x^c2)...(1+x+...+x^cm)

2. 这个方程的递归非常简单
   M(i,j) = summation(M(i-1, j-k)) where 0<= k <= cj M(i,j) = 0 j <= 0 M(i,1) = i given for every 1= 1 M(i,j) 是将 j 个球分配到前 i 个箱子中的方法数。

对于动态规划部分，通过记忆化来解决这个递归，您将自动获得 DP 解决方案。

- gibraltar

---

感谢Snape的评论。我之前也看到过你发布的公式，但它有些难以编码，不是很直观。 此外，我认为递归应该是- M（i，j）= sum（M（i-k，j-1）），其中0 <= k <= cj。 但这个递归不适合动态规划（或者说它不适用于吗？）。子问题不重叠。并且这只适用于一个{n，m和c1，c2......cm}集合（或每个集合分别工作），而我有多组测试用例。不同测试用例之间会有任何关系吗？如果我错了，请指出来。我的主要目的是DP。 - Andrew

哦，对于给定的测试集，子问题是重叠的。 - Andrew

谢谢你纠正我。这个解决方案只适用于某些测试用例。但是可以应用某种优化来快速解决多个测试用例的问题。我会尝试想出这样的优化方法。 - gibraltar