Hi,
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[1] problem and the Knapsack[2] problem.
[1] http://en.wikipedia.org/wiki/Bin_packing_problem
[2] http://en.wikipedia.org/wiki/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://blog.technomancy.org/tags/python.html 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.