使用动态规划将球分配到具有给定容量的"箱"中

Question

我想知道如何使用DP解决这样的问题.

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

我面临的问题是

1. 如何找到一个递归关系(我可以当容量都是一个单一的常数c).
2. 将有几个测试用例,每个测试用例都有自己的c1,c2 .... cm.因此DP如何实际应用于所有这些测试用例,因为答案明确取决于当前的c1,c2 .... cm,并且我无法存储(或预先计算)c1,c2的所有组合的答案. ...厘米.

另外,我也不能为这个问题提出任何直接的组合公式,我也不认为存在这个问题.

Answer 1

您可以定义函数，假设限制c[0], c[1], ...是固定的，然后编写递归公式，返回将 n 个球分配到从索引 k 开始的c[m-1]容器中的方式数。通过这种方法，基本公式很简单

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] + ...你知道不需要搜索就没有解决方案（并且你可以预先计算部分和）。