# How to distribute a number of elements in a bucket so that it is within a range?

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?

• Most variations of the knapsack problem are NP-complete, meaning that there probably isn't any feasible algorithm that will solve it optimally. That's a big hint for you right there: don't try finding an efficient, sound algorithm - there probably isn't one! Instead, use simple heuristics and live with the fact that you can't guarante a correct solution quickly. – Kilian Foth Oct 6 '15 at 10:34
• @KilianFoth I'm not sure that correct == optimal. ?? – 3Dave Oct 8 '15 at 2:04
• I think @KilianFoth is probably right here. To his point, have you tried just doing a simply minimizing algorithm where you sort the numbers and then just keep putting from biggest to smallest into the bucket with the least current sum? I suspect this will fail sometimes for sets that have valid solutions, but I also bet that this failure rate is pretty small with respect to random sets. – J Trana Oct 16 '15 at 4:27

You have `K` buckets, currently five.
Sort your positive input values, and find their sum, `s`. Verify that `100 × K ≤ s ≤ 150 × K`, or abort at once.
• @meolic, it's just obvious. Step (1), verify that `s` is in range, corresponds to OP's "neither less, nor more" requirement. Step (2), start with "hardest" items and assign them to lightest bucket, is a common heuristic, it's The Greedy Algorithm. No, it's not guaranteed to succeed in all cases that a solution exists. But it will produce a fairly tight packing with buckets filled to similar levels, so it works very well in practice. If you want to tackle combinatoric solutions, you'll find it more tractable to do that with the last M leftovers, where M is "small", M << 50. (Maybe 50 is small?) – J_H Dec 4 '18 at 23:22