Change Making Problem

When discussing greedy algorithms, a classic example is the "Change Making" problem. Suppose you need to pay a certain amount, and you only have bills with denominations of 1 yuan, 5 yuan, 10 yuan, 20 yuan, 50 yuan, and 100 yuan. The goal of the greedy algorithm is to pay using the minimum number of bills.

Steps

Here are the steps for an example of a greedy algorithm:

1. Initialize an empty list of bills to store the bills used during payment.
2. Sort the bill denominations in descending order.
3. Start with the largest denomination bill and use as many of them as possible to make the payment until no further payment can be made.
4. If the current denomination cannot pay the remaining amount, move to the next smaller denomination.
5. Repeat steps 3 and 4 until all amounts are paid.

For example, suppose you need to pay 126 yuan. Following the algorithm above, you would make the payment in the following steps:

1. Initialize an empty bill list.
2. Sort the bills by denomination in descending order: [100, 50, 20, 10, 5, 1].
3. Use a bill with a denomination of 100 yuan to make the payment; the remaining amount is 26 yuan.
4. Since 26 yuan cannot be paid using a 100 yuan bill, move to the next smaller denomination.
5. Use a bill with a denomination of 50 yuan to make the payment; the remaining amount is 26 - 50 = -24 yuan.
6. Since the remaining amount is negative, it indicates that the payment is complete.
7. The final list of bills used is [100, 50], totaling 150 yuan.

Solution

::: code-tabs
@tab Java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class GreedyChange {
    
    public static void main(String[] args) {
        int[] denominations = {100, 50, 20, 10, 5, 1};
        int amount = 126;
        
        Map<Integer, Integer> change = makeChange(denominations, amount);
        
        System.out.println("Change breakdown:");
        for (Map.Entry<Integer, Integer> entry : change.entrySet()) {
            int denomination = entry.getKey();
            int count = entry.getValue();
            System.out.println(denomination + " x " + count);
        }
    }
    
    public static Map<Integer, Integer> makeChange(int[] denominations, int amount) {
        Arrays.sort(denominations); // Sort denominations in descending order
        
        Map<Integer, Integer> change = new HashMap<>();
        
        for (int i = denominations.length - 1; i >= 0; i--) {
            int denomination = denominations[i];
            
            if (amount >= denomination) {
                int count = amount / denomination;
                change.put(denomination, count);
                amount -= denomination * count;
            }
        }
        
        return change;
    }
}

@tab Python

def make_change(denominations, amount):
    denominations.sort(reverse=True)  # Sort denominations in descending order
    change = {}
    
    for denomination in denominations:
        if amount >= denomination:
            count = amount // denomination
            change[denomination] = count
            amount -= denomination * count
    return change

denominations = [100, 50, 20, 10, 5, 1]
amount = 126
change = make_change(denominations, amount)
print("Change breakdown:")
for denomination, count in change.items():
    print(f"{denomination} x {count}")

@tab JavaScript

function makeChange(denominations, amount) {
    denominations.sort((a, b) => b - a); // Sort denominations in descending order
    const change = {};
    for (const denomination of denominations) {
        if (amount >= denomination) {
            const count = Math.floor(amount / denomination);
            change[denomination] = count;
            amount -= denomination * count;
        }
    }
    return change;
}

const denominations = [100, 50, 20, 10, 5, 1];
const amount = 126;
const change = makeChange(denominations, amount);
console.log("Change breakdown:");
for (const denomination in change) {
    console.log(`${denomination} x ${change[denomination]}`);
}

@tab Go

package main
import (
    "fmt"
    "sort"
)
func makeChange(denominations []int, amount int) map[int]int {
    sort.Sort(sort.Reverse(sort.IntSlice(denominations))) // Sort denominations in descending order
    change := make(map[int]int)
    for _, denomination := range denominations {
        if amount >= denomination {
            count := amount / denomination
            change[denomination] = int(count)
            amount -= denomination * int(count)
        }
    }
    return change
}
func main() {
    denominations := []int{100, 50, 20, 10, 5, 1}
    amount := 126
    change := makeChange(denominations, amount)
    fmt.Println("Change breakdown:")
    for denomination, count := range change {
        fmt.Printf("%d x %d\n", denomination, count)
    }
}

:::