找零钱问题

问题

当谈到贪婪算法时，一个经典的示例是"找零钱"问题。假设你需要支付一定金额，而你手上只有面额为1元、5元、10元、20元、50元和100元的纸币。贪婪算法的目标是用尽可能少的纸币来支付。

步骤

下面是一个贪婪算法的示例步骤：

初始化一个空的纸币列表，用于存放支付时所使用的纸币。
将纸币面额按从大到小的顺序排列。
从最大面额的纸币开始，尽可能多地使用该面额的纸币支付，直到无法再支付为止。
如果当前面额的纸币无法支付剩余金额，转到下一个面额较小的纸币。
重复步骤3和步骤4，直到支付完所有金额。

例如，假设你需要支付126元。按照上述算法，你会按以下步骤进行支付：

初始化空的纸币列表。
按面额从大到小的顺序排列纸币：[100, 50, 20, 10, 5, 1]。
使用面额为100元的纸币，支付金额，剩余金额为26元。
由于26元无法使用100元纸币支付，转到下一个面额。
使用面额为50元的纸币，支付金额，剩余金额为26 - 50 = -24元。
由于剩余金额为负数，说明支付完成。
最终使用的纸币列表为[100, 50]，共计150元。

题解

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); // 从大到小排序面额
        
        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;
    }
}

def make_change(denominations, amount):
    denominations.sort(reverse=True)  # 从大到小排序面额

    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}")

function makeChange(denominations, amount) {
    denominations.sort((a, b) => b - a); // 从大到小排序面额

    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]}`);
}

package main

import (
	"fmt"
	"sort"
)

func makeChange(denominations []int, amount int) map[int]int {
	sort.Sort(sort.Reverse(sort.IntSlice(denominations))) // 从大到小排序面额

	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)
	}
}

找零钱问题

# 找零钱问题

# 问题

# 步骤

# 题解

找零钱问题

问题

步骤

题解