Bin packing algorithm

1
votes

I have a kitchen heating meals from frozen, they need to produce meals to a head count order. The meals come in frozen sizes of portions such as 4's, 6's etc. The larger sizes have a lower cost per unit. So allowing waste, how do I calculate the sizes to complete an order at the lowest cost.

1
algorithmbin-packing
Seems like the answer is in your title.. – harold
Your question is so generic that you can only take one of the bin packing algorithms available for your language of choice and input your parameters. Where are you stuck? – Emil Vikström
No answer Andrew? I'll accept the first helpful response. – Neil

1 Answers

2
votes

This problem kind of sounds like the knapsack problem to me. I'm assuming that a greedy algorithm will not work here because there appear to be overlapping subproblems. You will probably have to use a dynamic programming algorithm which determines the minimum cost for a given head count by calculating the cost for all possible combinations of meal portions satisfying that head count.

I only pointed you in the right direction because this sounds like it might be homework. Either way this problem sounds like it can be reduced to one with a well-known solution.