# Have python divide a number by multiple divisors and give me how it was done.

Have python divide a number by multiple divisors and give me how it was done.

I have the divisors, 3, 4, 5.5, 6.5 available. I would like to divide 29, since no numbers go into 29, multiple must be used. I would also like for the highest divisors to be used. I have an example below:

5.5 * 4 + 3 + 4 = 29 (This is the best possible answer.)

Where as,

3 * 7 + 4 * 2 = 29(This is the wrong answer as the maximum divisors are not used.)

Is this even possible to be done? To have a user input a number and then have it divide and get the results: how it was divided?

Thanks,
Stan

Try recursion. To look for a solution with multiple divisors, you assume it contains 1 * the first divisor and look for a solution with all but that first divisor and the remaining sum, then you assume it contains 2 * the first divisor and look for a solution with all but that first divisor and the remaining sum, and so on.

1 Like

Shouldnâ€™t `5.5 + 6.5 + 4*2 + 3*3` be better?

1 Like

Is this is variation of the â€śmaking changeâ€ť problem?

You have four types of coins, a \$3 coin, \$4 coin, \$5.50 coin and \$6.50 coin, and need to make \$29 in change.

It is not clear what you mean by â€śthe highest divisorsâ€ť. That can mean three different things:

• One of the divisors (coins) is the highest, in your example that is 6.5. That coin must always be used.
• There are four coins given (3, 4, 5.5, 6.5). You must use the maximum number of distinct coins, which for numbers greater than 19, will be all four of them.
• You must maximize the total number of coins.

The first example fails all three meanings:

1. It doesnâ€™t use the largest coin, 6.5.
2. It doesnâ€™t use all four coins (uses 5.5, 3 and 4, misses 6.5).
3. The total number of coins is just 4+1+1 = 6, which is less than the second example which has 7+2 = 9 coins.