The problem
Suppose I have some balls and box types:
- Each ball has a different weight.
- Each type of box has its min and max capacity, and a penalty when used.
- There are unlimited number of boxes for each type.
How can I arrange the balls into the least boxes such that:
- The total weight of the balls in each box is within its min and max capacity.
- The total penalty of the used boxes is minimized.
- There may be multiple solutions. However, the accepted solution is where the total weight of the balls in each box is nearest to its max capacity.
Example
For example, there are 5 balls of weight 31, 14, 13, 12, 7 respectively, and 3 box types:
type│ min │ max │penalty
────┼─────┼─────┼───────
A │ 11 │ 20 │ 1
B │ 21 │ 30 │ 1
C │ 31 │ 40 │ 5
The possible combinations are:
boxTypes│ 31 │ 14 │ 13 │ 12 │ 7 │ penalty
────────┼────┼────┼────┼────┼────┼─────────
ABC │ C │ B │ B │ A │ C │ 7
BBC │ C │ B1 │ B2 │ B2 │ B1 │ 7
CC │ C1 │ C2 │ C2 │ C2 │ C1 │ 10
ACC │ C1 │ C2 │ C2 │ A │ C2 │ 11
and many other unlisted possibilities where the set of box types are the same or the penalty is just too high.
Notice that there are 2 solutions with the same penalty. However, considering the third condition:
boxTypes │ box1 │ box2 │ box3 │ shortfall
─────────┼──────┼──────┼──────┼──────────────────────────────────
ABC │ 12 │ 27 │ 38 │ (20-12) + (30-27) + (40-38) = 13
BBC │ 21 │ 25 │ 31 │ (30-25) + (30-25) + (40-31) = 19
The ABC box combination is chosen due to filling the most capacity of the boxes.
My code
I am currently recursively generating all combinations of the balls, and check whether there is a set of box that fits the ball groups.
I am able to improve the performance by:
- Early halt when a group weight is out of the maximum capacity (40 in this example)
- Limit the number of boxes (2 - 3 instead of 5, i.e. 1 box for each ball)
However, my solution still cannot handle more than 15 balls.
Is there a better algorithm other than bruteforce to solve this problem?