Best distribution algorithm
I am looking for the best allocation algorithm for the below scenario.
We have a requirement to say 18 pieces. I have stock on my shelf as follows.
Bin A - 10 Bin B - 6 Bin C - 3 Bin D - 4
The algorithm should suggest cells in the following order
Bin A (10), Bin D (4), Bin C (3)
In a real scenario, we have n number of boxes with different quantities. We need to find the optimal combination. The goal is to maximize the amount of placement.
You can help.
Regards, Shaju
a source to share
Your problem is similar to the problem of bin-packing and with a backpack problem .
Take a look at them and see how you can apply these techniques to your problem.
a source to share
If this is the real thing and not homework, then you can probably walk away with brute force. Try all bunker combinations 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: the best match is 17 using 10 + 3 + 4. This is if you want a selection of full bins that give you the highest number that does not exceed the target. Adjust the taste.
a source to share
You can try this:
Step 1.
Sort the bins by the amount of free space
The largest bit is at index 0, the smallest bit is at index Z, take the bins at index 0 until the total space is either what you are looking for or you have too much. If you have what you are looking for, stop. If not, continue.
Step 2.
Let's say the last bit you selected is in index L (you selected L + 1 cell). Now, starting from L in descending order, paging at index Lx with bins at index Zx. By doing these swaps, you are reducing the total. Stop replacing before the amount is below what you are looking for. If you have what you were looking for, stop. Otherwise, go to step 3.
Step 3.
Let's say you now have selected bins between 0 and LX and between Z and ZX, and the total is (slightly) higher than what you are looking for. Now, for each bin between 0 and LX, find the best bit between the indices LX + 1 and ZX-1 so you can swap it to reduce the total so that the total is exactly what you are looking for.
This algorithm is linear and gives you a great chance to find the perfect set of boxes.
I would be interested to hear if this works for you.
a source to share