Is there an algorithm to find the minimum number of times multiple numbers fit into one number?

Question

For example, lets say we have the number 100, and want to find the minimum number of times 2,3 and 4 fit in it. For this all of the given numbers must be used.

Ex. 4 can fit in 23 times, 3 twice, and 2 once, giving 28 as the minimum amount of times these numbers fit. What I did in my head is guess and check. I tried to come up with an algorithm by taking the sum of the other smaller numbers, subtracting from the total, and finding how many times the largest number fits into that one. Subtract the result of how many times that number fits by the number. From there the steps are repeated. Example:

100 & 2,3,4
2+3 = 5
100 - 5 = 95
4 fits in 95 23 times giving 92
4 * 23 = 92
100-92 =8
8-2 = 6
3 fits into 6 twice
8 - 6 = 2
2 fits into 2 once
end.
This does not work for all values though. Could you point me to the right direction? Thanks.

Answer 1

Let $N \geq 9$ be your number. We always need to take at least one $2, 3$, and $4$, so let's just take one of each to start with. This leaves us with the number $N - 9$, and there are only two cases to consider.

• If the number $N - 9$ is divisible by $4$, just take all $4$'s because being greedy clearly beats any other solution.

• If the number $N - 9$ is not divisible by $4$, then reduce it to a number that is divisible by $4$ (by taking $2$'s and $3$'s) with the fewest number of moves. There are a few sub-cases to consider here. Then we can take all $4$'s afterwards.

For your $N = 100$ case, we would first take one $2, 3,$ and $4$, which leaves us with $91$. Now $91$ isn't divisible by $4$, so we need to reduce it to a number that is divisible by $4$. The quickest way to do this is by taking $3$, which leaves us with $88$. Finally, we can take the remaining $22$ numbers to be $4$, which gives us $3 + 1 + 22 = 26$ as our final answer.

Answer 2

Suppose your numbers are $a,b,c,d$ and $a < b < c < d$ and the number you want to fit them into is $N$.

Let $P(N; d,c,b,a)$ be the best strategy where you must use each number at least once.

Well, if you must use each number at least once, that's the same as fitting them into $N - (a+b+c+d)$ where you don't have to use each number at least once and then using each one one more time. Call that $B(M; d,c,b,a)$ where $M = N-(a,b,c,d)$.

Now to minimize the number of uses we should maximize the use of the of the largest number $d$. There is a maximum number of times that $d$ goes into $M$. It is $k=\lfloor \frac Md\rfloor$. If we can then do $B(M- kd, c,b,a)$ we will be done. If we can't we are not done and have to try $B(M-(k-1)d, c,b,a)$ until we find one that works.

Example: If our numbers are $8,10,15,24$ and we want to fit then into $213$ we use them each once to get $8+10+15+24= 57$ and $213 -57 = 156$ and try to figure $B(156; 24,15,10,8)$.

$24$ goes into $156$ six times and $156-6*24 = 12$. So we want so see if we can do $B(12; 15, 10,8)$. $15$ goes into $12$ zero times so we want to see if we can do $B(12; 10, 8)$.

$10$ goes into $12$ once and $12 -10 = 2$ so we want to see if we can do $B(2;8)$ as $8 > 2$ we can not.

So we go back to trying to figuring out $B(12;10,8)$ but instead of $10$ going into $12$ once, we have it go in zero times. So we want to figure $B(12;8)$ and $8$ goeis into $12$ once. So we want $B(4,8)$ but $8>4$ so we can't.

So we go back to $B(156; 24, 15,10,8)$ but now consider $24$ going into $156$ only $5$ times. $5*24= 120$ and $156-120= 36$. So we want to solve $B(36; 15,10, 8)$.

$15$ goes into $36$ two times. $36-2*15 = 6$ so we want $B(6;10,8)$ which is impossible as $10, 8 > 6$. So we try $15$ in $1$ times; $36-15=21$ so we want $B(31;10,8)$. $10$ goes into $21$ two times but $B(1;8)$ is impossible as is $B(11;8), B(21;8)$.

So we try $15$ in $0$ times and $B(36; 10,8)$. $10$ goes into $36$ three times but $B(6; 8)$ is impossible. So we try $10$ two times. and $B(16; 8)$ is possible!

So we hae $8$ goes in $2$ timesto get $16$ and $10$ goes in $2$ times to get $36$ and $15$ goes in $0$ times and $24$ goes in$5$ times to get $156$ then everything goes in one more time.

$213 = 6*24 + 1*15+ 3*10 + 3*8$ and $6+1+3+3= 13$ is the minimum number of uses.