How can I create a greedy algorithm for this "balls and boxes" knapsack-like problem?

user_14566568 0
Viewed 611

Say that there are n balls, each with weight at most 1. We can assume that the weights of these balls are put in an array W[1..n] with 0 <= W[i] <= 1 for all i. The problem is to put these balls in a minimum number of boxes so that each box contains no more than two balls, and the total weight of the balls placed in each box is <= 1.

I am to design an efficient greedy algorithm for this. I presume that one obvious choice (pick the largest first and the smallest second) is not correct. But what if I picked the largest available ball first, and then the largest remaining that fits second? I think this is right, but I'm not sure how to prove this. Doing this would produce a trivial O(n^2) algorithm.

This also seems like some kind of variant on the knapsack problem, but there the greedy algorithm is not optimal.

greedy algorithm
1 Answers

The usual proof template for greedy algorithms is to show that the algorithm's first k choices can be extended to an optimal solution, for all k ≥ 0 by induction on k. As it turns out, both of your ideas are correct, as is every greedy algorithm that repeatedly puts the largest remaining ball in a box together with (if possible) any ball that will go with it.

The base case of the induction, k = 0, is trivial. For the step, consider an optimal solution that agrees with the greedy solution for the first k−1 boxes. Let B be the heaviest ball not in the first k−1 boxes. Greedy packs B in box #k. Consider the possibilities.

  • If box #k appears in the optimal solution, then the latter fulfills the condition required for induction.

  • If the greedy solution has B in a box by itself, then B does not fit with any remaining ball, so the optimal solution also has B by itself, and the first k decisions agree.

  • If greedy has B with another ball but optimal has B alone, then we can modify the optimal solution by moving the other ball to B's box. This new solution is also optimal and fulfills the condition required for induction.

  • If greedy and optimal have B with different balls, then we can swap those balls in the optimal solution to align it with the greedy solution. We know that this is possible because the balls in the other box cannot be bigger than B, since the k−1 that may be larger than B are packed the same way in both solutions.

Your second solution can be implemented in O(n log n) time using a balanced binary search tree.

user_21446690
Related