Write the pseudocode of the greedy algorithm for the change-making problem, with an amount n and coin denominations d1, d2, …, dn as its input. What is the time efficiency class of your algorithm?

ChangeMaking.java

import java.util.Comparator;
import java.util.TreeSet;

public class ChangeMaking {
    static TreeSet<Integer> coins = new TreeSet<>(Comparator.reverseOrder());
    static int amount = 126;

    public static void main(String[] args) {
        coins.add(50);
        coins.add(25);
        coins.add(10);
        coins.add(5);
        coins.add(1);


        for (int d :
                coins) {
            if (amount - d >= 0) {
                double tmp = Math.floor(amount / d);
                System.out.println("amount: " + amount + " coin: " + d + " * " + tmp + " = " + d * tmp);
                amount -= d * tmp;
            }
        }
    }
}

ΙsampleOutput.txt

amount: 126 coin: 50 * 2.0 = 100.0
amount: 26 coin: 25 * 1.0 = 25.0
amount: 1 coin: 1 * 1.0 = 1.0