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

2

u/dougie0341 Jan 26 '16

Since you're asking the user for the number of inputs I would use a for loop. Traditionally you use a while loop when you don't know how many times you want to execute some task.

1

u/[deleted] Jan 26 '16

Ok, I can remove the while loop and change it to a for loop, but still, what about the rest of what I wrote? I don't want to be disrespectful, but your text didn't give me anything at all to be honest.
I wondered how I should think when it comes to this kind of algorithms, and if someone could like tell me some information that would help, but ok, thanks anyway.

1

u/dougie0341 Jan 26 '16

well this really isn't a simple algorithm especially for someone who is new to programming. But to me, the simplest way would be to add every single different combination and compare them. I would do this using a recursive function that checked every combination for each number so it would look something like this:

numbers: 1 2 3

possible combinations:

1, 1+2, 1+2+3, 1+3, 2, 2+3, 3

This would be a simple brute force way.

1

u/[deleted] Jan 26 '16

Would you use Set? HashSet?

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.

0

u/[deleted] Jan 26 '16

[deleted]

0

u/[deleted] Jan 26 '16
  1. I mean of course 1000 (one thousand).

  2. I believe I need to find all permutations, or do I?
    I dont think there are another way then try all the variations to see whats closest to 1000.

Like in the example, if my 4 numbers would be 500, 498, 400 and 4. Then without the variations I wouldn't find 1002, only 998 (500+498) I think.

0

u/[deleted] Jan 26 '16

[deleted]

1

u/[deleted] Jan 26 '16

Yes.
Like /r/bilal132 said, this is a power-set, I need to collect all numbers that comes in (a, b, c, d), then add in variations (a, a+b, a+b+c, a+b+c+d, a+c, a+d and then take b... and so on).

I think I need to use hashSet? Set? Dont think its a good idea with ArrayList.
I cant find any examples that are close to this one, something that should give any code/tutorial. Will read more about Sets.

Thanks.

0

u/[deleted] Jan 26 '16

[deleted]

1

u/[deleted] Jan 27 '16

That is a good thing, that it don't allow duplicates.
I will guarantee that the user only puts in Integers under 1000 in value.
Now I need to read more about Set and see how it works, thanks.