Жадный алгоритм java на карте

Question

Я работаю над эмулятором ATM в java. Общий шаблон в проекте - Command. Итак, у меня есть 4 команды - getInfo, депозит, вывод и выход.

У меня проблемы с реализацией жадного алгоритма в методе вывода. Он должен возвращать карту сначала. Целое число - это «деноминация», а второе целое число «количество» осталось в банкомате после того, как мы вышли.

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

Таким образом, в качестве аргумента требуется ожидаемая сумма и его вычесть из банкомата с наименьшим количеством счетов.

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 
    { 


    } 
} 

Так что мне нужен этот метод, чтобы вернуть карту или бросить исключение, если сумма спрашивает «expectedAmount» выше, то деньги доступны в банкомате.

Если взять $ 600 это может быть - три счета: $ 500 + $ 50 + $ 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; 
    }