java - 用B个球填充N个号码箱有几种不同的方法

假设您有N个料箱，其中每个料箱的容量为K。您还有B个球。所有球都可以通过几种不同的方式分配到垃圾箱中？

我正在尝试通过编写一个具有以下参数的函数来解决此问题：

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

   }

我不确定如何解决这个问题。我知道N = 0时的答案是0。而B = 0时N> 1的答案是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;
    }
}