Optimum pack size purchases

xenium
xenium used Ask the Experts™
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:
https://docs.google.com/spreadsheets/d/1TMiCPLrCq4pI-SjYUz_AhBY8g_duXlIKfDvOAZo0EC8/edit#gid=531556003

Many thanks
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
ozo
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.

Author

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

Can anyone provide the formulation for this particular problem?
Bill PrewTest your restores, not your backups...
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
CompTIA Security+

Learn the essential functions of CompTIA Security+, which establishes the core knowledge required of any cybersecurity role and leads professionals into intermediate-level cybersecurity jobs.

"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.

Author

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:
A dynamic programming approach might start with tables containing f_mincost(0), f_minwaste(0),
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

Author

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?
ozo
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.

Author

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

https://docs.google.com/spreadsheets/d/1TMiCPLrCq4pI-SjYUz_AhBY8g_duXlIKfDvOAZo0EC8/edit#gid=271767874

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

Author

Commented:
I could use the functions SPLIT, QUERY etc

Author

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

Author

Commented:
btw the following sheet implements one method to match a delimited list to a bucket list and output an array of counts:
https://docs.google.com/spreadsheets/d/1TMiCPLrCq4pI-SjYUz_AhBY8g_duXlIKfDvOAZo0EC8/edit#gid=866273639

This sheet output uses the following formula. Buckets are semi-colon delimited in cell C2, and data is comma-delimited in cell C3:
=mmult(arrayformula(if(arrayformula(split(C3,",")=transpose(split(C2,";"))),1,0)),transpose(split(rept("1,",columns(split(C3,","))-1)&"1",",")))

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial