Рассчитать различные способы сделать (деньги) изменения от $ 167,37?

Question

Это был вопрос для собеседования:

Учитывая сумму, скажем, $ 167,37, найдите все возможные способы получения изменения для этой суммы, используя деноминации, доступные в валюте?

Любой, кто мог бы придумать эффективный по времени и времени алгоритм и поддерживающий код, пожалуйста, поделитесь.

Вот код, который я написал (работает).Я пытаюсь найти время выполнения этого, любая помощь приветствуется

    import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;


public class change_generation {

    /**
     * @param args
     */

    public static void generatechange(float amount,LinkedList<Float> denominations,HashMap<Float,Integer> useddenominations)
    {
        if(amount<0)
            return;
        if(amount==0)
        {
            Iterator<Float> it = useddenominations.keySet().iterator();
            while(it.hasNext())
            {
                Float val = it.next();
                System.out.println(val +" :: "+useddenominations.get(val));
            }

            System.out.println("**************************************");
            return;
        }

        for(Float denom : denominations)
        {

            if(amount-denom < 0)
                continue;

            if(useddenominations.get(denom)== null)
                useddenominations.put(denom, 0);

            useddenominations.put(denom, useddenominations.get(denom)+1);
            generatechange(amount-denom, denominations, useddenominations);
            useddenominations.put(denom, useddenominations.get(denom)-1);
        }

    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        float amount = 2.0f;
        float nikle=0.5f;
        float dollar=1.0f;
        float ddollar=2.0f;

        LinkedList<Float> denominations = new LinkedList<Float>();


        denominations.add(ddollar);
        denominations.add(dollar);
        denominations.add(nikle);

        HashMap<Float,Integer> useddenominations = new HashMap<Float,Integer>();
        generatechange(amount, denominations, useddenominations);
    }

}

Answer 1

РЕДАКТИРОВАТЬ

Это конкретный пример проблемы комбинации / подмножества, ответ здесь.

Поиск всех возможных комбинаций чисел для достижения заданной суммы

--- Я сохраняю свой ответ ниже (поскольку он был кому-то полезен), однако, по общему признанию, это не прямой ответ на этот вопрос ---

ОРИГИНАЛЬНЫЙ ОТВЕТ

Наиболее распространенным решением является динамическое программирование:

Сначала вы найдете самый простой способ внести изменение в 1, затем вы используете это решение, чтобы внести изменения в течение 2, 3, 4, 5, 6 и т. Д. .... На каждой итерации вы «проверяете», можно перейти «назад» и уменьшить количество монет в вашем ответе. Например, до «4» необходимо добавить копейки. Но как только вы доберетесь до «5», вы можете удалить все пенни, и для вашего решения требуется только одна монета: никель. Но затем, до 9, вы снова должны добавить копейки, и т. Д. И т. Д.

Однако методология динамического программирования не гарантируется как быстрая.

Кроме того, вы можете использовать жадный метод, при котором вы постоянно выбираете как можно большую монету. Это очень быстро, но не всегда дает вам оптимальное решение. Однако, если ваши монеты 1 5 10 и 25, Greedy работает отлично и намного быстрее, чем метод линейного программирования.

Answer 2

Памятка (вид) ваш друг здесь. Простая реализация в C:

unsigned int findRes(int n)
{
   //Setup array, etc.

   //Only one way to make zero... no coins.
   results[0] = 1;

   for(i=0; i<number_of_coins; i++)
   {
       for(j=coins[i]; j<=n; j++)
       {
           results[j] += results[j - coins[i]];
       }
   }

   return results[n];
}

Итак, что мы действительно здесь делаем, так это говорим:

1) Наш единственный возможный способ сделать 0 монет - это 0 (это наш базовый случай)

2) Если мы пытаемся вычислить значение m, давайте проверим каждую монету k. Пока k <= m, мы можем использовать эту монету k в решении </p>

3) Ну, если мы можем использовать k в решении, то не могли бы мы просто взять решение для (m-k) и добавить его к нашему текущему итогу?

Answer 3

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;

public class change_generation {

  static int jj=1;

  public static void generatechange(float amount,LinkedList<Float> denominations, 
                                  HashMap<Float,Integer> useddenominations) {
    if(amount<0)
        return;
    if(amount==0) {
        Iterator<Float> it = useddenominations.keySet().iterator();
        while(it.hasNext()) {
            Float val = it.next();
            System.out.println(val +" :: "+useddenominations.get(val));
        }
        System.out.println("**************************************");

        return;
    }

    for(Float denom : denominations) {
        if(amount-denom < 0)
            continue;
        if(useddenominations.get(denom)== null)
            useddenominations.put(denom, 0);

        useddenominations.put(denom, useddenominations.get(denom)+1);
        generatechange(amount-denom, denominations, useddenominations);
        useddenominations.put(denom, useddenominations.get(denom)-1);
    }
  }

  public static void main(String[] args) {
    float amount = 2.0f;
    float nikle=0.25f;
    float dollar=1.0f;
    float ddollar=2.0f;

    LinkedList<Float> denominations = new LinkedList<Float>();

    denominations.add(ddollar);
    denominations.add(dollar);
    denominations.add(nikle);

    HashMap<Float,Integer> useddenominations = new HashMap<Float,Integer>();
    generatechange(amount, denominations, useddenominations);
  }
}

Answer 4

Не используйте поплавки, даже малейшие неточности разрушат ваш алгоритм.

Переход от самой большой к самой низкой монете / банкноте.Для каждой возможной суммы вызовите функцию рекурсивно.Если монет больше не осталось, оплатите оставшиеся и распечатайте решение.Вот как это выглядит в псевдо-C:

#define N 14

int coinValue[N]={20000,10000,5000,2000,1000,500,200,100,50,20,10,5,2,1};
int coinCount[N];

void f(int toSpend, int i)
{

    if(coinValue[i]>1)
    {
        for(coinCount[i]=0;coinCount[i]*coinValue[i]<=toSpend;coinCount[i]++)
        {
            f(toSpend-coinCount[i]*coinValue[i],i+1);
        }
    }
    else
    {
        coinCount[i]=toSpend;
        print(coinCount);
    }

}

Answer 5

Я бы попробовал смоделировать это в реальной жизни.

Если бы вы были на кассе и знали, что должны были найти 167,37 доллара, вы, вероятно, изначально рассматривали бы 200 долларов как "самый простой" тендер, так как всего двазаметки.Тогда, если бы у меня было это, я мог бы рассмотреть 170 долларов, то есть 100 долларов, 50 долларов и 20 долларов (три примечания).Видите, куда я иду?

Более формально, попробуйте сделать чрезмерный тендер с минимальным количеством банкнот / монет.Это было бы намного легче перечислить, чем полный набор возможностей.