如何在不排序的情况下递归解决m个盒子和n个不同大小的球问题？

Question

我有 m 个盒子和 n 个球，每个都有不同的大小。举个简单的例子，假设我们有大小为 [10, 50, 20] 的盒子和大小为 [20, 10, 30, 10] 的球。可以这样解决，

盒子 0（尺寸 10）可以存放球 1（尺寸 10）或球 3，但为了简单起见，我们以球 1 为例。

盒子 1（尺寸 50）可以存放球 0（尺寸 20）和球 2（尺寸 30）

盒子 2（尺寸 20）可以存放球 3（尺寸 10）

为了解决这个问题，我写了下面的 java 代码，它是使用排序和迭代的方式解决的，

boolean canBallsFitInBoxes(int [] boxes, int [] balls) {
    Arrays.sort(boxes);
    Arrays.sort(balls);
    int j = 0;
    int i = 0;
    for(; i < balls.length && j < boxes.length;) {
      if(boxes[j] >= balls[i]){
        boxes[j] -= balls[i];
        i++;
      } else {
        j++;
      }
      
    }
    
    return i == balls.length;
}

我测试了几个案例，上面的迭代解决方案有效。我可能错过了边缘案例，很高兴听到他们纠正它。

我自己尝试了递归版本，但只有当给定的数组已经排序或者盒子和数组可以像 (boxes: [10, 50, 20] and balls: [10, 20, 30, 10])。基本上，当盒子或球的顺序混乱时，我正在努力寻找使用递归的解决方案。

但我正在尝试找到解决此问题的通用方法。有什么建议我如何在没有显式排序的情况下递归解决它？

Answer 1

A brute-force，解决问题的递归方法是取球 n 并尝试将其放入每个盒子中。如果球适合当前盒子，递归使用下一个球，否则尝试下一个盒子。

public boolean canBallsFitInBoxes(int[] boxes, int[] balls) {
  return fits(boxes, balls, 0);
}

private boolean fits(int[] boxes, int[] balls, int currentBall) {
  // More balls available?
  if (currentBall >= balls.length)
    // No -> all balls are inside boxes already -> success
    return true;
  // Check each box, trying to insert current ball
  for (int currentBox = 0; currentBox < boxes.length; currentBox++) {
    // Does ball fit into box?
    if (boxes[currentBox] >= balls[currentBall]) {
      // Yes -> put ball into box
      boxes[currentBox] -= balls[currentBall];
      // Proceed to remaining balls (recursively)
      if (fits(boxes, balls, currentBall + 1))
        // All remaining balls fit -> success
        return true;
      else
        // At least one of the remaining balls does not fit -> remove current ball from box again
        boxes[currentBox] += balls[currentBall];
    }
  }
  // All tries for this ball failed -> back-trace
  return false;
}

如果你不喜欢递归方法开始时的成功检查，而更愿意在递归之前检查，你也可以使用：

private boolean fits(int[] boxes, int[] balls, int currentBall) {
  // Check each box, trying to insert current ball
  for (int currentBox = 0; currentBox < boxes.length; currentBox++) {
    // Does ball fit into box?
    if (boxes[currentBox] >= balls[currentBall]) {
      // Yes -> put ball into box
      boxes[currentBox] -= balls[currentBall];
      // If more balls are available, proceed to remaining balls (recursively)
      if (currentBall + 1 >= balls.length || fits(boxes, balls, currentBall + 1))
        // All remaining balls fit -> success
        return true;
      else
        // At least one of the remaining balls does not fit -> remove current ball from box again
        boxes[currentBox] += balls[currentBall];
    }
  }
  // All tries for this ball failed -> back-trace
  return false;
}

不懂算法的欢迎提问

如何在不排序的情况下递归解决m个盒子和n个不同大小的球问题？

How do I solve m boxes and n balls of different size problem recursively without sorting?

java

recursion