java - 用 B 个球填充 N 个箱子有多少种不同的方法

Question

假设你有 N 个箱子，每个箱子的容量为 K。你还有 B 个球。有多少种不同的方式可以将所有球分配到箱子中？

我试图通过编写一个接受以下参数的函数来解决这个问题:

public static int waysBin(int ball, int bin, int capacity) 
   {
      //code here

   } 

我有点不确定如何解决这个问题。我知道当N = 0时，答案是0。当B = 0，N>1时，答案是1。

但是，我不确定如何计算其他所有组合。我想以递归和动态的方式解决这个问题。

Answer 1

这样想:如果你有 n 个球填充 b 个容量为 k 的箱子，那么你可以用 0 到 k 个球填充第一个箱子(称为数字 c)。对于这些可能性中的每一种，您都可以用 n-c 球填充剩余的 b-1 箱子。如果您只有 1 个垃圾箱，那么如果您的球数少于容量，则有一种组合，否则为零。

所以:

int combinations(int ballCount, int binCount, int binSize) {
    if (binCount > 1) {
        return IntStream.rangeClosed(0, Math.min(ballCount, binSize))
            .map(c -> combinations(ballCount - c, binCount - 1, binSize))
            .sum();
    } else {
        return binCount == 0 || ballCount > binSize ? 0 : 1;
    }            
}

如果您没有 Java 8，请使用:

int combinations(int ballCount, int binCount, int binSize) {
    if (binCount > 1) {
        int combos = 0;
        for (c = 0; c <= Math.min(ballCount, binSize); c++)
            combos += combinations(ballCount - c, binCount - 1, binSize);
        return combos;
    } else {
        return binCount == 0 || ballCount > binSize ? 0 : 1;
    }            
}