地图中的贪婪算法java

Question

我正在研究java中的ATM模拟器。项目中的整体模式是命令。所以我有 4 个命令 - 获取信息、存款、取款和退出。

我在提款方法中实现贪婪算法时遇到问题。它应该返回地图，第一个整数是"面额"，第二个整数是我们提款后留在 ATM 中的"金额"。

public Map<Integer, Integer> withdrawAmount(int expectedAmount) 

因此，它以预期金额作为论据，并且必须用尽可能少的钞票从ATM中减去它。

   public class CurrencyManipulator
    {
// denominations is a map where each denomination and it's quantity stored
        private String currencyCode;
        private Map<Integer, Integer> denominations = new HashMap<>();
        public String getCurrencyCode()
        {
            return currencyCode;
        }
    public CurrencyManipulator(String currencyCode)
    {
        this.currencyCode = currencyCode;
    }
    public void addAmount(int denomination, int count)
    {
        if (denominations.containsKey(denomination))
        {
            denominations.put(denomination, denominations.get(count) + count);
        } else
        {
            denominations.put(denomination, count);
        }
    }
    public int getTotalAmount()
    {
        int sum = 0;
        for (Map.Entry<Integer, Integer> pair : denominations.entrySet())
        {
            sum = pair.getKey() * pair.getValue();
        }
        return sum;
    }
    public boolean hasMoney()
    {
        return denominations.size() != 0;
    }
    public boolean isAmountAvailable(int expectedAmount)
    {
        return expectedAmount <= getTotalAmount();
    }
     public Map<Integer, Integer> withdrawAmount(int expectedAmount) throws NotEnoughMoneyException
    {

    }
} 

因此，如果要求的"预期金额"高于 ATM 中的可用资金，我需要此方法返回地图或抛出异常。

如果我们拿 600 美元，它可能是 - 三张账单：500 美元 + 50 美元或 200 美元 +

200 美元 + 200 美元，首选选项是 500 美元 + 50 美元 + 50 美元例如，您必须提供 600 美元自动柜员机的账单数量如下：

500 - 2

200 - 3

100 - 1

50 - 12

岁

结果应该是：

500 - 1

100 - 1

这是我想到的：

public Map<Integer, Integer> withdrawAmount(int expectedAmount) throws NotEnoughMoneyException
    {
        denominations.put(50,1);
        denominations.put(500,1);
        denominations.put(200,3);
        HashMap<Integer, Integer> map = new HashMap<>();
        TreeMap<Integer, Integer> sortedMap = new TreeMap<>(Collections.reverseOrder());
        sortedMap.putAll(denominations);
        ArrayList<Integer> bills = new ArrayList<>();
        bills.addAll(sortedMap.keySet());

        int num;
        for (int i = 0; i < bills.size(); i++)
        {
            if (bills.get(i) <= expectedAmount)
            {
                num = expectedAmount / bills.get(i);
                map.put(bills.get(i), num);
                expectedAmount -= num * bills.get(i);
            }
        }
        System.out.println(map);
        return map;
    }

它返回所需账单及其数量的映射。

现在我的问题是..如何将其与我拥有的"面额"地图进行比较并从中减去新地图？

Answer 1

如果

有人需要它，它似乎是工作代码

public Map<Integer, Integer> withdrawAmount(int expectedAmount) throws NotEnoughMoneyException
    {

        denominations.put(50,2);
        denominations.put(500,1);
        denominations.put(100,1);
        HashMap<Integer, Integer> map = new HashMap<>();
        TreeMap<Integer, Integer> sortedDenominations = new TreeMap<>(Collections.reverseOrder());
        sortedDenominations.putAll(denominations);
        ArrayList<Integer> bills = new ArrayList<>();
        bills.addAll(sortedDenominations.keySet());

        int num;
        for (int i = 0; i < bills.size(); i++)
        {
            if (bills.get(i) <= expectedAmount)
            {
                num = expectedAmount / bills.get(i);
                map.put(bills.get(i), num);
                expectedAmount -= num * bills.get(i);
            }
        }
        System.out.println(map);
        for (Map.Entry<Integer,Integer> denominPresent:sortedDenominations.entrySet()){
            int value;
            for (Map.Entry<Integer,Integer> deominNeeded:map.entrySet()){
                if(denominPresent.getKey().equals(deominNeeded.getKey())){
                    value = denominPresent.getValue()-deominNeeded.getValue();
                    if (value>=0) sortedDenominations.put(denominPresent.getKey(),value);
                    else throw new NotEnoughMoneyException();
                }
            }
        }
        System.out.println(sortedDenominations);
        return sortedDenominations;
    }

Answer 2

另一种解决方案。如果使用树状图初始化面额变量，将起作用

...
private Map<Integer, Integer> denominations = new TreeMap<>(Comparator.reverseOrder());
...
public Map<Integer, Integer> withdrawAmount(int expectedAmount) throws NotEnoughMoneyException {
    final Map<Integer, Integer> map = new TreeMap<>(Comparator.reverseOrder());
    // calculate denomination map to cash
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        int denomination = entry.getKey();
        if (denomination <= expectedAmount) {
            int num = Math.min(expectedAmount / denomination, entry.getValue());
            map.put(denomination, num);
            expectedAmount -= num * denomination;
        }
        if (expectedAmount == 0) {
            break;
        }
    }
    if (expectedAmount != 0) {
        throw new NotEnoughMoneyException();
    }
    map.forEach((key, value) -> {
        denominations.compute(key, (denomination, count) -> {
            return (count == value) ? null : count - value;
        });
    });
    return map;
}