# Optimum pack size purchases

on
hi,

Say you're shopping for some ingredients which come in standard pack sizes of either 100g, 250g or 500g, having prices \$0.40, \$0.75 and \$1.00 respectively.

Depending on the exact quantity you need, you can choose to optimise your choice of pack purchases according to price or minimum wastage, or perhaps some combination of the two.

For example if you need 350g, you could buy 1 x 500g pack for \$1.00, and waste 150g, or buy 1 x 250g + 1x100g at a cost of \$1.15 and have no wastage.

Given the quantity you need, how could you optimise your pack selection mathematically? (a) for minimum cost, and (b) for minimum wastage?

ie some function(quantity needed) gives the pack sizes and quantities to buy, eg:
f_mincost(350) outputs 1 x 500g
f_minwaste(350) outputs 1 x 250g, 1 x 100g

Here is a spreadsheet with some more examples:

Many thanks
Comment
Watch Question

Do more with

EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Most Valuable Expert 2014
Top Expert 2015
Commented:
Dynamic Programming https://en.wikipedia.org/wiki/Dynamic_programming would be the solution method that springs to mind.

Commented:
Thanks, sounds good, though it's been a few decades since I did DP.

Can anyone provide the formulation for this particular problem?
Top Expert 2016
Commented:
Not a full answer for you, but a related question from the past that you might want to review for possible ideas...

Excel batch combination optimiser

»bp

Commented:
"Depending on the exact quantity you need, you can choose to optimise your choice of pack purchases according to price or minimum wastage, or perhaps some combination of the two."
The essential step in solving this problem is to put a monetary value on the waste.  This process depends on your circumstances and your values. Only you can determine this.

Commented:
DP could be the way. If so I'm guessing that

1. the stages are the pack sizes, so there are 3 stages: 100g, 250g, 500g

2. the nodes are the number of packs per size from zero upto minimum needed to meet demand with just one pack size
= -integer(-350/packsize)                  (This rounds up 350/packsize to nearest whole number)
eg stage for pack size 100g has 5 nodes: 0,1,2,3,4

3. the arcs have 2 values: pack price and quantity

To find a solution:
a) eliminate paths where total quantity <350
b) select path with minimum cost

I'm not sure if (a) is part of DP or not though. Probably need to play around with this a bit.
Most Valuable Expert 2014
Top Expert 2015
Commented:
then generate the  f_mincost(n), f_minwaste(n) using the tables of f_mincost(0 ... n-50), f_minwaste(0 ... n-50),
which should be either f_mincost(n-100)+\$0.40 or f_mincost(n-250)+\$0.75 or f_mincost(n-500)+\$1.00
or  f_minwaste(n-100)+100 or  f_minwaste(n-250)+250 or f_minwaste(n-500)+500

Commented:
THanks that looks promising, it's really late here so not got my head around it, will check again in the morning.

Does the 50 refer to the greatest common divisor of 100, 250, 500?
Most Valuable Expert 2014
Top Expert 2015

Commented:
You could extend by +1 each time, but if you observe that f_min(1001) must be the same as f_min(1050), you can see that you can save time and space if you extend by +50 instead.

Commented:
Ok thanks, I think we're there...

Note: some formula are formatted with comments: to view this double-click on the cell

Ideally instead of column K I'd like an array result, eg f_mincost(1050) = {1,0,2}
to correspond to the pack size array which is {100, 250, 500}
indicating that the required quantities are 1 x 100g + 2 x 500g

Any ideas how to create this neatly?

Thanks

Commented:
I could use the functions SPLIT, QUERY etc

Commented:
Great stuff thanks for your valuable inputs in solving this.

Commented:
btw the following sheet implements one method to match a delimited list to a bucket list and output an array of counts: