Need some help with an equation(s) for a basic Java program

[Billogi]

I am writing a basic program using Java. The function is to break up any number the user inputs into smaller values, the catch is that these smaller values have a maximum usage and the overall result has to use the combination with the highest amount of values. I am figuring out the code just fine. I have made a class for the values to define their value, max value and max usage, it is the maths I am struggling with.

For example, the input is 377. I need to break it down into a *maximum* of twenty 1's, twenty 2's and one hundred 5's but my desired result has to be the most long winded, so in this case 17 1s, 10 2s and 68 5's. So I need to be able to figure out the maximum amount of 1s to allow the maximum amount of 2s to ,in turn, allow the maximum amount of 5s. And this needs to work with any number the user inputs.

I would later add higher numbers with set maximum usage and a finally the value of 100 with infinite useage. For now I just need a few equations to work with.

Can anyone shed a little light on a few possible ways of doing this? thanks =)

 

[MarkFL]

Can you explain further the process of breaking down a number? For the example input of 377, you cite at least 20 1's, 20 2's and 100 5's, but the sum of these is 560. I am not sure then what you mean by breaking a number down. How does the resulting breakdown come about?

 

[Billogi]

Well, with my example it would need to be broken down into 17 1s, 10 2s and 68 5's as that would give you the maximum number of individual values used (rather than say 1 1, 3 2s and 74 5s).

Sorry, I did say at least, I meant a maximum of! I've been on it for hours now, think it is time for a rest ha

 

[MarkFL]

I'm afraid I am still unclear about what you are doing.

What is to stop you from exchanging one of the 5's for five 1's?

 

[Nono713]

MarkFL - there can be at most 20 1's, 20 2's and 100 5's, that's why you can't add an extra five 1's. That said, you can add another 10 2's by sacrificing four 5's, or even an extra three 1's and one extra 2 by removing one 5, so I still don't understand what is being optimized either.

Did you mean a maximum of twenty 1's, ten 2's and a hundred 5's?​

 

[MarkFL]

Yes, I did forget the constraint on the 1's and 2's. :D

 

[MarkFL]

It seems to me if N is the input, an algorithm (pseudo-code) which might work is:

let ones be the number of 1's
let twos be the number of 2's
let fives be the number of 5's

get input N

if N > 20 then

     ones = 20

else

     ones = N

end if

N = N - ones

if N > 10 then

     twos = 10

     elseif N > 0 then

          twos = N/2

     else

          end program

end if

N = N - 2*twos

if N > 0 then

     let R = mod(N,5)

     if R = 0 then

          fives = N/5

     else

          if R = 1 then

               twos = twos - 2
               N = N + 4

          elseif R = 2

               twos = twos - 1
               ones = ones - 1
               N = N + 3

          elseif R = 3

               twos = twos - 1
               N = N + 2

          elseif R = 4

               ones = ones - 1
               N = N + 1

          end if

          fives = N/5

     end if

end if

N = N - 5*fives

if N != 0 then

     ERROR

else

     end program

end if

Note: I have not tested this code, but see if this works for you. If N > 540, then you will get fives > 100.

I have edited it for the constraint that there be ten 2's.

 

[MarkFL]

I have moved this topic to this sub-forum since it does not really fit with the usual topics posted in the Pre-Algebra and Algebra sub-forum. I feel this sub-forum is the best fit because of the interdisciplinary description.

We try to keep the topics here organized in the most useful manner for our members, but please do not feel that you have done anything wrong, as topics like this can be tricky to decide where best to post. :D

 

[Billogi]

Did you mean a maximum of twenty 1's, ten 2's and a hundred 5's?​

Ah, yes I did! It's amazing what spending over four hours trying to solve a problem can do to your thought process =P

Well, my thought process at least

And Mark, thank you for the help with the pseudo-code. I will give it a try tonight :)

 

[MarkFL]

You will have to amend the code I wrote a bit then for the constraint that there be a maximum of ten 2's. :D

edit: I made the change already.