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

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

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

我面临的问题是

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

另外，我也无法为这个问题想出任何直接的组合公式，而且我认为也不存在。

您可以假设限制来定义您的函数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] + ...那么你就知道不需要搜索就没有解决方案（并且你可以预先计算部分和）。