使用动态编程计算在多个值的箱中有多少个球 [英] Calculating How Many Balls in Bins Over Several Values Using Dynamic Programming

问题描述

关于将N个相同的球放入M个不同的纸箱中并打印所有组合的经典问题:如果您想通过打印所有情况来扩展问题，该怎么办?M，N 蛮力方法可以像这样完成:

Regarding the classic problem of putting N identical balls into M distinct bins and printing all the combinations: What if you would want to extend the problem by printing all cases 0< M, N The brute force method could be done something like this:

for (int i =0; i<M; i++)
{  
   for (int j =0; j <N; j++)
   {
        PrintAllCombinations(j,i)
   }
}

现在，如果我们研究前一对m和n的输出，我们会看到每个先前迭代的输出是下一个迭代的子集.在我看来，我们可以应用动态算法来利用这一现象.但是，由于我们仍然需要对每个 n 进行分区，例如 n = 3 = 3 + 0、2 + 1、1 + 2 .我们仍然需要做很多多余的组合计算.
有什么想法需要改进吗?

Now if we study the output of the first couple m and n, we see that the output of each previous iteration is a subset of the next. It seems to me that we can apply a dynamic algorithm to exploit this phenomenon. However, because we still need to partition every n, for example n=3 = 3 +0, 2+1, 1+2. we still need to do alot of redundant combination calculations.
Any ideas fir improvments?

推荐答案

让 S [i] [j] 为 i 球在中的组合数> j 个垃圾箱.

S [0] [j] = 1 ，因为唯一的组合是将所有垃圾箱都清空.

S[0][j] = 1 for all j since the only combination is to have all bins empty.

S [i] [1] = 1 ，因为唯一的组合就是将所有球都放在一个箱中.

S[i][1] = 1 for all i since the only combination is to put all the balls in the one bin.

对于每隔一个i，j S [i] [j] = sum(x = 0-> i，S [i-x] [j-1]).也就是说，对于每个其他位置，您可以通过将每个可能的球数分配给最后一个箱并求和得到的组合数来计算组合数.

For every other i, j S[i][j] = sum(x = 0 -> i, S[i-x][j-1]). That is for every other position you can compute the number of combinations by assigning every possible number of balls to the last bin and sum the number of combinations you get.

如果要打印出组合，可以将计数替换为实际组合，并在将内部组合作为总和时附加值 x .这将占用大量内存，而速度却不会大大提高.只需进行递归并重复计算，因为无论如何您都会受到解决方案数量的限制.

If you want to print out the combinations you can replace the count with the actual combinations and append the value x when you take the internal combinations in the sum. That will take a lot of memory without a lot of gain in speed. Just do the recursion and repeat the computation since you're bound by the number of solutions anyway.

这篇关于使用动态编程计算在多个值的箱中有多少个球的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！