solution_greedy_coins.java

public class Coin {
    private int value;
    private int quantity;
    Moneda(int value, int quantity) {
        this.value = value;
        this.quantity = quantity;
    }
    /* getters & setters */
}

/* This is actually the "hard" part */
int selectCandidate(ArrayList < Integer > values) {
    int biggest = Integer.MIN_VALUE;
    for (Integer coin: values)
        if ((biggest < coin)) biggest = coin;
    return biggest;
}

/* Now the actual schema */

ArrayList < Coin > greedySchema(ArrayList < Integer > values, int quantity) {
    /* We initialize our solution structure */
    ArrayList < Coin > solution = new ArrayList < Coin > ();
    /* Any auxiliary variable is ok */
    int value;
    
    while ((quantity > 0) && (!values.isEmpty())) {
        /* Select and remove the coin from our monetary system */
        value = selectCandidate(values);
        values.remove(new Integer(value));
        
        /* If this is true, it meanwe can still look for coins to give */
        if ((quantity / value) > 0) {
            solution.add(new Coin(value, quantity / value));
            /* This will lower the quantity we need to give back */
            quantity = quanity % value;
        }
    }
    
    /* Once the quantity is 0 we are DONE! */
    if (quantity == 0) {
        return solution;
    } else return null;
}