分配球成“垃圾桶给定容量”使用动态规划 [英] Distribution of balls into 'bins with given capacities' using Dynamic Programming

问题描述

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

I was wondering how to solve such a problem using DP.

给定n个球和M箱，每个箱子有最大容量C1，C2，...厘米。什么是散发这n个球放入这些米仓方式的总数量。

Given n balls and m bins, each bin having max. capacity c1, c2,...cm. What is the total number of ways of distributing these n balls into these m bins.

我面临的问题是

1. 如何找到一个递推关系（我可以当的能力都是一个常数c）。
2. 将有几个试验的情况下，每一个具有自己的一组c1，c2的....厘米。因此，如何将在DP实际上适用于所有这些测试用例，因为答案明确地依赖于present C1，C2 ....厘米，我不能存储（或pre-计算）的所有答案C1，C2 ....厘米。
的组合

另外，我不能拿出任何直接combinatoric公式为这个问题太多了，我不认为存在了。

Also, I could not come up with any direct combinatoric formula for this problem too, and I don't think one exists too.

推荐答案

您可以定义你的函数假设的限制 C [0] ，Ç [1] ... C [M-1] 固定，然后写递推公式返回的方式，你可以分发数量ñ球放入箱开始索引k 。这种方法的一个基本公式很简单

You can define your function assuming the limits c[0], c[1], ... c[m-1] as fixed and then writing the recursive formula that returns the number of ways you can distribute n balls into bins starting at index k. With this approach a basic formula is simply

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'GT; C [K] + C [K + 1] + C [K + 2 + ... 那么你就知道有没有解决方案，而无需进行搜索（你可以precompute的部分和）。

then you need to add memoization (this will be equivalent to a DP approach) and some other optimizations like e.g. that if n > c[k] + c[k+1] + c[k+2] + ... then you know there are no solutions without the need to search (and you can precompute the partial sums).

这篇关于分配球成“垃圾桶给定容量”使用动态规划的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！