mardi 7 novembre 2017

Efficient one pass algorithm for finding a set of 'N' numbers whos sum is equal to 'M'?

What must be efficient algorithm for the given problem statement? (java preferred)

Find a set S of N numbers such that their sum is equal to M. Each number in the set S must fall within the given deviation 'D' from the average M/N.

int M= 100;
int N= 10;
int D= 3;

Here average of M/N = 10. So with deviation of 3, N can be one of the numbers from {7,8,9,10,11,12,13}

Result must be similar to this set:

11 11 9 8 11 9 11 11 9 10

Below the is the program, I came up so far:

    public class RandomNumberGenerator {

    public static void main(String args[]) {
        Random r = new Random();
        int sum = 100;
        int numbers = 10;
        int deviation = 3;

        int iterator = 0;
        int sumTemp = 0;
        int storeArray[] = new int[numbers];
        int average = Math.round((float) sum / (float) numbers);
        int numberOfAttempts = 0;
        int discardedBecauseGreater = 0;
        System.out.println("Average is " + average);

        while (iterator < numbers) {
            int temp = r.nextInt(average + deviation);
            if (temp > average - deviation) {
                storeArray[iterator] = temp;
                sumTemp += temp;
                iterator++;
            }
            if (iterator == numbers) {
                if (sumTemp == sum) {
                    System.out.println("Got the result " + sumTemp);
                    System.out
                            .println("Number of attempts " + numberOfAttempts);
                    System.out.println("Discarded because of greater "
                            + discardedBecauseGreater);
                    for (int i = 0; i < numbers; i++) {
                        System.out.println(storeArray[i]);
                    }

                    break;
                } else {
                    numberOfAttempts++;
                    sumTemp = 0;
                    iterator = 0;
                }
            }

            if (sumTemp > sum) {
                discardedBecauseGreater++;
                sumTemp = 0;
                iterator = 0;
            }

        }
    }
}




Aucun commentaire:

Enregistrer un commentaire