Generate and distribute random numbers fairly in java

Question

Hi I have been trying to figure this quiz out

A lottery company shares out prizes to winning contestants every week. Most weeks, more than one contestant wins, in which case they try to share out the prizes as fairly as possible. Their prize distribution office has hired you to write a program that they will use to distribute prizes in the fairest way possible.

The program you write should take two lines of input:

• A comma-separated list of this week's prizes' values
• A comma-separated names of this week's winners

For example, the input could be: 100,800,200,500,400,1000 Joshua,Mahesh,Lilian

The program should then output the fairest possible distribution of prizes, by displaying one line for each winner, with the values of the prizes allocated to them. For example, given the input above, the output could be:

• Joshua:100,400,500
• Mahesh:1000
• Lilian:800,200

The example above gives a perfect solution, where all winners get the same value of prizes (total value of 1000 each). In many cases, this will not be possible, but all prizes must be distributed and cannot be divided. Part of your job is to decide how you define 'fair' for these cases. For example, given the input

400,400,500,600

Barry,Sheila,Onyango,Wekesa

The following would be acceptable output, because there is no fairer distribution possible:

• Barry:400
• Sheila:400
• Onyango:500
• Wekesa:600

I am using java and so far this is what I have come up with

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    private static String amounts;
    private static String names;

    public static void main(String[] args) {
        Scanner userInput = new Scanner(System.in);

        System.out.print(
                "Please enter the lottery amounts separated by commas: ");

        if (userInput.hasNext()) {
            amounts = userInput.next();
            // System.out.println("You entered: " + amounts);
        }

        System.out.print("Please enter the contestants names: ");

        if (userInput.hasNext()) {
            names = userInput.next();
            // System.out.println("You entered: " + names);
        }

        String amountArray[] = amounts.split(",");
        String nameArray[] = names.split(",");

        award(nameArray, amountArray);
    }

    // Method that awards the amounts to the winners
    public static void award(String names[], String amounts[]) {
        int randomAmount;
        int randomName;

        for (int i = 0; i < amounts.length; i++) {
            randomAmount = (int) (Math.random() * amounts.length);
            int usedValue[] = new int[amounts.length];
            usedValue[i] = randomAmount;
            if (checkValueUsed(randomAmount, usedValue)) {

                randomName = (int) (Math.random() * names.length);
                int usedName[] = new int[names.length];

                System.out.println(names[randomName] + " = "
                        + amounts[randomAmount]);
            } else {
                break;
            }
        }
    }

    private static boolean checkValueUsed(int currentState, int[] myArray) {
        boolean found = false;

        for (int i = 0; !found && (i < myArray.length); i++) {
            if (myArray[i] == currentState) {
                found = true;
            }
        }
        return found;
    }

    private void checkUsedValue(int currentState, int[] myArray) {
        for (int i = 0; (i < myArray.length); i++) {

            if (myArray[i] == currentState) {

            }
        }
    }
}

My idea of fair is to select a random amount and assign it to a random winner.

Answer 1

1) This looks like an interview/exam question. I'm not to judge but... really?
2) Your idea of fair is NOT what is intended. By the examples given, fair means all prizes are distributed and each winners total is as close to each other as possible.
3) From the above - this is a known problem. A greedy algorithm is likely to perform well. (I can't really see why not, unless you get very specific on the optimization part of the problem)