4

I have to distribute newspapers, and the printing company gives it to me in bundles of $15$ and $25$, now if a store wants $115$ I will have to send them $4 \times 25$ and $1 \times 15$, or if they want $55$ I will send them $1 \times 25$ and $2 \times 15$.

And I would rather send bundles of $25$ then $15$, so if they ask for a $150$ copies, I want to send them $6$ bundles of $25$ and not $10$ of $15$.

Is there a formula to find the best combination of the $2$ bundle sizes to send to my customers?

Ivo Terek
  • 77,665
Joel Weiss
  • 43
  • A sample algorithm could be: given $x$ denoting the newspaper number, you may want to maximise the 25 bundle, so you have to divide $x$ by 25: $x=25A+r$. Then you have to divide $r$ by 15 so: $r=15B+r_1$. If $_1$ is zero you can satisfy the request and you will have maximised the 25 bundle. – 7raiden7 Jul 02 '14 at 16:44
  • This is part of the Coin problem – Ross Millikan Jul 02 '14 at 16:47

2 Answers2

3

Are they guaranteed to make an order size that can be made up of 15s and 25s?

If so, subtract 15s from the order amount until what is left is divisible by 25, and then divide by 25 to get the number of 25 bundles.

You will never need to use more than four 15 bundles (If you used five, you could replace them with three 25 bundles), so this should go relatively quickly, and will use as many 25s as possible, since you use the minimum number of 15s to get to a point where what is left is divisible by 25.

qaphla
  • 3,890
0

The lowest common multiple of 25 and 15 is 75. So assume the printing company gives a number $n$ that can be expressed as a finite sum of 25s and 15s. If $n$ is divisible by 25, then you are done. Otherwise, subtract by 15 until the result is divisible by 25. You will only need to subtract 4 times at the most because 75 is 15*5.

Edward ffitch
  • 2,188