找零算法开发需求：基于HashMap实现最少货币找零

Got it, let's tackle this change-making problem with the key twist: we're limited by the seller's actual wallet stock (not infinite denominations). The goal is to return the minimum number of coins/bills for the required change amount—here's how to approach it properly:

核心思路 #

Unlike the classic greedy algorithm (which works for infinite, "canonical" denominations like euros), we need to account for limited stock. Dynamic Programming (DP) is the way to go here because it tracks the minimum count of coins/bills needed for every amount up to the target, while respecting the available quantity of each denomination.

Step-by-Step Breakdown #

1. Preprocess Denominations

   • First, sort denominations from largest to smallest (this helps prioritize higher values, which naturally reduces the total count when possible).
   • Filter out any denominations with 0 quantity in the seller's wallet—no need to waste cycles on those.

2. DP Array Initialization

   • Create a dp array where dp[amount] stores the minimum number of coins/bills needed to make amount cents (using cents avoids floating point errors).
   • Initialize all values to Integer.MAX_VALUE (representing "impossible to make this amount") except dp[0] = 0 (making 0 change requires 0 items).

3. Track Combinations for Backtracking

   • We also need a way to reconstruct the actual coins/bills used, not just the count. Use a map amountToCoins where each entry maps an amount to the combination of denominations that makes it with the minimum count.

4. Fill the DP Array

   • For each denomination, iterate from the target change amount down to the denomination's value (this prevents reusing the same denomination more times than available).
   • For each possible number of the current denomination (from 1 to its available count), check if using that many would result in a lower total count for the current amount. If yes, update the dp value and the corresponding combination.

5. Reconstruct the Result

   • If dp[targetChange] is still Integer.MAX_VALUE, return an empty map (meaning the seller can't make the required change). Otherwise, return the combination stored in amountToCoins for the target amount.

Concrete Code Example (Java) #

Since your example uses a HashMap for the seller's wallet, here's a Java implementation that fits perfectly:

import java.util.*;

public class ChangeMaker {
    public static Map<Integer, Integer> makeChange(int targetChange, Map<Integer, Integer> sellerWallet) {
        // Sort denominations descending and filter out unused ones
        List<Integer> denominations = new ArrayList<>(sellerWallet.keySet());
        denominations.sort(Collections.reverseOrder());
        denominations.removeIf(denom -> sellerWallet.get(denom) == 0);

        // DP array: dp[amount] = min number of coins/bills needed
        int[] dp = new int[targetChange + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        // Track which coins make up each amount (for backtracking)
        Map<Integer, Map<Integer, Integer>> amountToCoins = new HashMap<>();
        amountToCoins.put(0, new HashMap<>());

        for (int denom : denominations) {
            int availableCount = sellerWallet.get(denom);
            // Iterate backwards to avoid overcounting the same denomination multiple times
            for (int amount = targetChange; amount >= denom; amount--) {
                // Try using 1 to availableCount of this denomination
                for (int useCount = 1; useCount <= availableCount; useCount++) {
                    int prevAmount = amount - useCount * denom;
                    if (prevAmount >= 0 && dp[prevAmount] != Integer.MAX_VALUE) {
                        if (dp[prevAmount] + useCount < dp[amount]) {
                            dp[amount] = dp[prevAmount] + useCount;
                            // Clone the previous combination and add current denom usage
                            Map<Integer, Integer> newCombination = new HashMap<>(amountToCoins.get(prevAmount));
                            newCombination.put(denom, newCombination.getOrDefault(denom, 0) + useCount);
                            amountToCoins.put(amount, newCombination);
                        }
                    }
                }
            }
        }

        // Return empty map if change can't be made
        return dp[targetChange] == Integer.MAX_VALUE ? Collections.emptyMap() : amountToCoins.get(targetChange);
    }

    public static void main(String[] args) {
        // Example seller wallet (values in cents: 5000 = 50€, 1000=10€, etc.)
        Map<Integer, Integer> sellerWallet = new HashMap<>();
        sellerWallet.put(5000, 18);
        sellerWallet.put(1000, 2);
        sellerWallet.put(500, 1);
        sellerWallet.put(200, 5);
        sellerWallet.put(10, 3);

        int targetChange = 7210; // 72€10¢
        Map<Integer, Integer> changeCombination = makeChange(targetChange, sellerWallet);

        System.out.println("Minimum change combination:");
        for (Map.Entry<Integer, Integer> entry : changeCombination.entrySet()) {
            String label = entry.getKey() >= 100 ? (entry.getKey() / 100) + "€" : entry.getKey() + "¢";
            System.out.printf("%s: %d %s%n", label, entry.getValue(), entry.getValue() == 1 ? "piece" : "pieces");
        }
        // Output: 50€: 1 piece, 10€: 2 pieces, 2€: 1 piece, 10¢: 1 piece (total 5 pieces)
    }
}

Key Notes #

• Avoiding Floats: Using cents (integer values) prevents precision errors that come with using euros as floats.
• Edge Cases: Handles cases where the target change is 0 (returns empty map), or the seller can't make the change (also returns empty map).
• Efficiency: The DP approach runs in O(targetChange * totalDenominations * averageCount) time, which is efficient for typical real-world change amounts.

内容的提问来源于stack exchange，提问作者Jéwôm'