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

user_3906965 0
Viewed 78

I've m boxes and n balls, each of different size. To give a simple example, let's say we have boxes of size: [10, 50, 20] and balls of size: [20, 10, 30, 10]. It can solved as follows,

Box 0 (Size 10) can store Ball 1 (Size 10) or Ball 3, but let's take Ball 1 for simplicity.

Box 1 (Size 50) can store Ball 0 (size 20) and Ball 2 (size 30)

Box 2 (Size 20) can store Ball 3 (size 10)

To solve this problem, I wrote following is the java code which is solved using sorting and in iterative way,

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;
}

I tested for few cases and above iterative solution works. I might have missed edge cases, happy to hear them correct it.

I tried recursive version by myself, but it works only if given arrays are already sorted or when boxes and arrays can be mapped easily like (boxes: [10, 50, 20] and balls: [10, 20, 30, 10]). Basically, when the order of boxes or balls is jumbled, I'm struggling to find a solution using recursion.

But I'm trying to find a generic way to solve this problem. Any suggestions how can I solve it recursively without explicit sorting?

recursion java
1 Answers

A brute-force, recursive way of solving the problem would be to take ball n and try to put it into each box. If the ball fits into the current box, recurse into using the next ball, otherwise try the next box.

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;
}

If you do not like the success check at the beginning of the recursive method and would rather prefer to check before recursing, you could also use:

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;
}

Feel free to ask, if you do not understand the algorithm.

user_10826810
Related