算法：将y个球放入x个盒子中，其中x <= y。

Question

算法：将y个球放入x个盒子中，其中x <= y。

4

我正在开发一个安卓应用，遇到了一个问题：

有 x 个盒子和 y 个球，其中 x <= y，我想按顺序将这些球分配到盒子里。例如：3个盒子，盒子 A，盒子 B 和 盒子 C，5个球，球1，球2，球3，球4，球5。

我需要将第一个球球1放在盒子A中，将球5放在盒子C中，其余的球均匀地放置在所有盒子中（不要紧如果某个盒子中的球比其他盒子多）。以下是模拟此问题的循环（缺少增量值）：

int boxCount = 0; // first box is 0 and last box is x
int numOfBalls = y;
for(int i = 0; i < numOfBalls; i++, boxCount += ???)
{
    boxes.get(boxCount).add(balls.get(i));
}

我应该使用什么等式来解决这个问题，而不是???？

编辑：

由于x <= y，这意味着：

没有一个盒子应该是空的。
盒子之间的球数差异不应超过1。

编辑2：

所谓“in order”，指的是这个顺序：

A   B   C
---------
1   3   5
2   4

不是

A   B   C
---------
1   2   3
4   5

- Eng.Fouad

只是为了澄清，您想要在盒子上均匀分布球吗？ - Yet Another Geek

@YetAnotherGeek 如果一个盒子里的球比其他盒子多，这并不重要。 - Eng.Fouad

@Eng.Fouad 抱歉，我是指均匀间隔的分布。 - Yet Another Geek

2

你还有其他的限制吗？比如说，把除了最后一个球以外的所有球放在第一个盒子里是否是可接受的解决方案？ - Oliver Charlesworth

3

请明确说明如何在盒子中分配小球。 - moooeeeep

显示剩余3条评论

4个回答

3

你可以将 (int)n/k 个球分配给前面的 k-1 个盒子，然后将剩余的球放进最后一个盒子。这样编码会更简单。

使用以下代码：boxCount += (i % (numOfBalls/numOfBoxes) == 0 && boxCount < numOfBoxes-1 ? 1 : 0)

- amit

这将把3个球放入第一个盒子中。 - David Harkness

@DavidHarkness：当然，谢谢。我误解了我在第一行写的+=语句...现在它正在执行描述中所说的操作。但是，我看到问题已经被编辑过了，OP也在寻找更加均匀分布的东西。 - amit

我尝试了这个，但它给了我 A: [1]、B: [2]、C: [3, 4, 5]。 - Eng.Fouad

@Eng.Fouad：正如我在评论中所述，它解决了最初的问题，即在编辑之前询问“最多相差1”。我将其留在这里，因为它可能会帮助其他人... - amit

2

int ball = 0;
for( int box = 0; box < x; ++box )
   while ( x * (ball+1) <= y * (box+1) )
      boxes.get(box).add(balls.get(ball++));

循环不变式：左侧的k个盒子包含了球的k/x的分数（四舍五入）。

- Ben Voigt

这给了我：A: [1]，B: [2, 3]，C: [4]，它舍弃了 5。 - Eng.Fouad

@Eng.Fouad：抱歉，在while条件中使用<=而不是<。已应用修改。 - Ben Voigt

谢谢，伙计。现在它运行得非常好。不过，我已经接受了@Saphrosit的答案，因为他比你先发布了 :) - Eng.Fouad

没问题，他比我更需要这些分数。 - Ben Voigt

1

好的，再试一次：

boxCount = ((i * nbrOfBoxes) / nbrOfBalls) + 1;

请注意，球的索引从0到4编号（与for循环中一样）。如果您希望boxCount以零为基础，请删除+ 1。

- matsev

java.lang.IndexOutOfBoundsException: Index: 3, Size: 3 - Eng.Fouad

盒子A到C的索引是多少？如果是 0..2，则按建议移除 +1。 - matsev

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Manlio · Accepted Answer

int flag;
int lastBallAdded = 0;
int k = numOfBalls/numOfBoxes;
int m = numOfBalls%numOfBoxes;

for(int i = 0; i < numOfBoxes; i++, lastBallAdded+=k+flag) {
    flag = i<m;

    for(int j=lastBallAdded;j<lastBallAdded + k + flag;j++) 
        boxes.get(i).add(balls.get(j));
}

这是这个解决方案的原理：

根据问题的定义，算法应该将k = numOfBalls/numOfBoxes个球放在每个盒子里，除了前m = numOfBalls%numOfBoxes个盒子，在这些盒子中，您应该放置k+1个球。

您也可以将其改写为：

int i;
for(i = 0; i < m; i++) {
    //add k+1 balls
}

for(;i<numOfBoxes; i++) {
    //add k balls
}