Calculate the most efficient combination of lengths

Question

I have coils of rope for sale that come pre-packaged in the following sizes:

• 10cm
• 20cm
• 50cm
• 100cm

Somebody walks into the store and wants to purchase 280cm of rope. I want to sell them the most efficient combination of my available coil sizes.

By most efficient, I mean with the least amount of wasted rope for the customer.

Could somebody suggest a method or formula I could use to calculate this?

Answer 1

The solution is to use the largest pre-packaged rope size until you can't anymore, then use the $2^{\text{nd}}$ largest, then so on, until you have reached the desired purchase size or just over the desired purchase size.

e.g. for something more exotic, say $437$cm,:

$437$ divides $100$ $4$ times ($100$ cm $\times$ $4$ count)

$37$cm remains.

$37$cm divides $20$ $1$ time ($20$cm $\times$ $1$)

$17$cm remains.

$17$cm divides $20$ almost $1$ time ($20$cm $\times$ $1$)

$7$cm doesn't divide any of our rope sizes, so we'll have to bump the order up to $440$cm of rope.

Totals:

• $100$ cm $\times$ $4$ count
• $20$cm $\times$ $2$ count

---

The question is, how can we make a formula for this? How can we make a mathematical formula that you could plug in to in order to get the numbers of each package that constitute an order?

I suggest:

$$100w + 50x + 20y + 10z = \text{ceil}(\text{order}/10)*10$$

w=floor(ceil(o/10)*10 /100);
x=floor(ceil((o-100w)/10)*10 /50);
y=floor(ceil((o-100w-50x)/10)*10 /20);
z=floor(ceil((o-100w-50x-20y)/10));
o=437

(you can paste the above into wolframalpha.com)

This will work in any typical online math calculator (just put a ; between each equation), such as here in wolframalpha.

Picture of wolframalpha: