r/learnjava • • Jan 26 '16

Unsolved Problem with a simple Algorithm.

Hi guys.

Pre:

A friend of mine gave me this and told me to use the console & the Scanner class.

Add together numbers until you come as close to 1.000(high&low) as possible, BUT IF two numbers are equally close to 1.000, choose the highest one.
The first number you write in to the console should be the number that tells how many numbers you will put in.

For an example.
I will put in 4 numbers in the console, (4, 900, 500, 498, 4)
If you add 500 with 498, you will get 998. That is close to 1.000,
but if you add 500 with 498 and 4, you will get 1.002.
998 & 1002 are equally close to 1.000, so then I need the program to choose the 1.002 and not the 998.

The problem I have is the Algorithm. How do I do this?
I can count every number I put together and do it while the sum are under 1.000, but then I will miss the 1.002.
I know that I can use the Math.max to compare 2 sums to see if they are equally far away from 1.000 and then choose the biggest of them.
But yes, I don't understand how you should think here.

This is what i have done right now, it just add all numbers you put in together, and as I said, the first number you write in the console will just tell the program how many numbers it will be put in.

So the question is, how do you think when it comes to this?
What goes in your head when you try to write the algorithm. You have any solution or help?
Thanks.

public class Main {

    public static void main(String[] args) {

        int numbers = 0, count;
        Scanner scn = new Scanner(System.in);
        count = scn.nextInt();

        while (scn.hasNextInt()) {
            numbers += scn.nextInt();
            count--;

            if (count == 0) {
                System.out.println(numbers);
            }
        }
    }
}
0 Upvotes

9 comments sorted by

View all comments

2

u/[deleted] Jan 26 '16

As mentioned before this is not exactly a simple algorithm. What you want to do is find the power set of the original set after that you would want to loop through the power set get the sum of all the subsets and compare them to see which is closest to a thousand.

The following two references should help you out:

https://en.wikipedia.org/wiki/Power_set

http://stackoverflow.com/questions/1670862/obtaining-a-powerset-of-a-set-in-java

1

u/anonafun Jan 28 '16

Exactly. This is not a simple algorithm.