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

Python Help
1

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

2

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
3

Shouldn’t 5.5 + 6.5 + 4*2 + 3*3 be better?

1 Like
4

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.

Better answers:

  1. 5.5 * 1 + 6.5 * 1 + 3 * 3 + 4 * 2 # Uses all four coins, and seven coins in total.
  2. Your “wrong answer” has 7+2 = 9 coins, so better still.

Before solving this problem, you need to decide what the problem really is first.

1 Like