Best Allocation Algorithm

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

---

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.

---

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.

---

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.