5

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?

Improve this question
3
  • 6
    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, 2015 at 10:34
  • @KilianFoth I'm not sure that correct == optimal. ??
    – 3Dave
    Oct 8, 2015 at 2:04
  • 1
    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, 2015 at 4:27

2 Answers 2

Reset to default
2

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.

Improve this answer
1

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.

Greedily process each input value, from largest to smallest, and assign it to a bucket. In one variant of the algorithm, deterministically assign it to the currently lightest bucket. In a more expensive variant, assign it at random to an eligible bucket, and be prepared for some amount of backtracking or retries if things don't initially work out.

Improve this answer
2
  • I need more info about this idea. What is the name of the presented algorithm?
    – meolic
    Dec 4, 2018 at 22:18
  • 1
    @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, 2018 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.