algorithm - 使用动态规划将球分配到 'bins with given capacities'

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], ... 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] + ... 那么你知道没有不需要搜索的解决方案(你可以预先计算部分和)。