I have an algorithm that I am not sure whether to classify as a greedy algorithm or a brute force algorithm.

while(true) {
            int n = 0;
            int d = 0;
              int r = 0;
              int outcome = 0;
            
            n = scan.nextInt();
            d = scan.nextInt();
            r = scan.nextInt();

            if ( n   d   r == 0) break;

            int[] morning = new int[n];
            int[] afternoon = new int[n];

            for (int i = 0; i < n; i  ) {
                morning[i] = scan.nextInt();
            }
            for (int i = 0; i < n; i  ) {
                afternoon[i] = -scan.nextInt();
            }

            for (int i = 0; i < n; i  ) {
                int sum = morning[i]   (-afternoon[i]) - d;
                if (sum > 0) outcome  = sum * r;
            }
            System.out.printf("%d\n", outcome);
        }

I feel like it is most likely greedy, not completely certain.

CodePudding user response：

So at first glance, and without further information, it does not seem to me that this algorithm uses greedy or brute force techniques.

By definition a greedy algorithm makes decisions at each step by choosing the locally optimal choice, with the hope of finding a global optimum, and a brute force algorithm tries every possible solution to a problem, in order to find the correct solution.

It doesn't appear that that piece of code does either of those things.

CodePudding user response：

A Greedy algorithm is one that limits the amount of work it has to do by making certain assumptions about data values it receives along the way. Your code is definitely not greedy, as it is going to perform the same logic on every value in the incoming data set.

An algorithm is "brute force" if it takes a naive approach to solving a problem that will consume considerably more resources (time and/or memory) than another algorithm that is able to limit resource usage by being more clever in its approach to the problem.

So if your algorithm is brute-force or not, IMO, comes down to if there could be a more efficient way to process the same data and arrive at the same answer. Looking at your code, it isn't obvious to me how there could be a more efficient way to do what it is doing. For that reason, I don't think your algorithm could be said to be brute-force.