I have 50 elements n1, n2, n3, … , n50 and a limited number of buckets, say 5 buckets and each bucket can hold a range from, say 100 to 150 only (which is nothing but the sum of the elements in that bucket), but neither less than 100, nor more than 150.
Which algorithm is most suitable for solving this problem, such that all the 5 buckets are used and all the elements (n1, n2, n3, …) are also used up?
If a bucket cannot be used or if any element must be left out, then the algorithm should just return "InvalidConditionsFound".
I tried Knapsack which gives you a combination as close to a given number, but how to get it within a range and also make sure that it chooses wisely such that all the buckets are getting filled, and not that two bucket gets 150 full and the other bucket is only at, say 50?
Best Answer
50 elements x 5 buckets? Those are small numbers. A brute-force backtracking heuristic will probably work. Sort them, add elements to buckets trying to keep the bucket totals equal. If you don't get a solution in one pass, then back-track.
I once used a similar process to assign pallets of goods to trucks. The goal was to minimize the number of trucks required to contain all the pallets. Each truck had a maximum weight capacity (and a pallet limit). First I followed Best-Fit-First to load the theoretical minimum number of trucks. If I had pallets left over I found the two emptiest trucks and did a brute-force repacking to see if I could squeeze in one more pallet. This algorithm successfully packed 200 pallets with a total weight of 499,000 pounds into 10 trucks with a capacity of 50,000 pounds each.