Best Allocation Algorithm

Question

I am looking for a best allocation algorithm for the below scenario.

We have requirement for say 18 pieces. I have the stock in my shelf as follows.

Bin A - 10 Bin B - 6 Bin C - 3 Bin D - 4

Algorithm should propose the bins in the following order

Bin A(10) , Bin D (4), Bin C (3)

Real scenario we have n number of bins with different quantities.We need to find the optimal combination. Objective is to maxmize the allocation quantity.

Can you please help.

Regards, Shaju

Welcome to stack overflow :). It would be useful if you could tell us what you've tried already and where exactly you're stuck; at the moment it sounds like you're trying to get us to do your homework for you. — Andrew Aylett, Apr 22 '10 at 08:41
Possible duplicate: http://stackoverflow.com/questions/140406/how-can-i-programmatically-determine-how-to-fit-smaller-boxes-into-a-larger-packa — Matthieu M., Apr 22 '10 at 09:53

score 6 · Answer 1 · edited May 15 '13 at 00:57

6

Your problem is similar to the bin-packing problem and the knapsack problem.

Look into those and see how you can apply those methods to your problem.

edited May 15 '13 at 00:57

templatetypedef

362,284
104
897
1,065

answered Apr 22 '10 at 08:43

Cristina

1,991
3
17
24

redtuna · Answer 2 · 2013-05-15T00:51:31.943

0

If this is a real-world thing and not homework then you can probably get away with brute force. Try all combinations of bins and see which is best.

In Python, use the superset function from http://www.technomancy.org/python/powerset-generator-python/ and then:

>>> bins=[10,6,3,4]
>>> tgt=18
>>> max( [ y<=tgt and (y,x) for (y,x) in [(sum(x),x) for x in powerset(bins)]])
(17, [10, 3, 4])

so there you go: best match is 17, by using 10+3+4. That's if you want the choice of full bins that give you the largest number that's at most the target. Adjust to taste.

edited May 15 '13 at 00:51

answered Apr 22 '10 at 21:32

redtuna

4,586
21
35

1

If it is real-world thing - do not try bruteforce way described above. – Maciej Łopaciński May 14 '13 at 12:51
6

seriously, just because an algorithm is exponential doesn't necessarily mean it's bad: it really depends on the scale you need it at. This solution is 3 lines, it's trivial to test for your size. With 10 bins the answer is instant, with 20 bins it takes 10 seconds. So long as there aren't more than 20 bins in the poster's shelf, this should work just fine. – redtuna May 15 '13 at 00:45

score -1 · Answer 3 · edited Apr 18 '15 at 20:01

You could try this:

Step 1.
Sort the bins by the amount of space available
The largest bin has index 0, the smallest bin has index Z pick bins start from index 0, until the total space is either what you are looking for or you've got too much. If you've got the total you are looking for, stop. If not, carry on.

Step 2.
Let's say the last bin you picked is at index L (you've picked L+1 bins). Now starting from L descending, swap bins at index L-x with bins at index Z-x. By doing these swaps you are reducing the total. Stop swapping before the total is below what you are looking for. If you have a total that you were looking for, stop. Otherwise to step 3.

Step 3.
Let's say you've now picked the bins between index 0 and L-X and between Z and Z-X and the total is (slightly) above what you are looking for. Now for each bin between 0 and L-X, find the best bin between index L-X+1 and Z-X-1 that you could swap it with to reduce the total so the total is exactly what you are looking for.

This algorithm is linear and gives you a great chance of finding a perfect set of bins.

I'd be interested to hear if this works for you.

Best Allocation Algorithm

3 Answers3