Алгоритм определения комбинаций монет

Question

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

Задача состоит в том, чтобы написать программу для определения всех возможных комбинаций монет для кассира, чтобы вернуть их в качестве изменения.основанный на ценности монеты и количестве монет.Например, может существовать валюта с 4 монетами: 2 цента, 6 центов, 10 центов и 15 центов.Сколько существует комбинаций, равных 50 центам?

Я использую язык C ++, хотя это не имеет большого значения.

edit: это более конкретныйвопрос программирования, но как мне проанализировать строку в C ++, чтобы получить значения монет?Они были даны в текстовом документе, например

4 2 6 10 15 50 

(где числа в данном случае соответствуют приведенному мною примеру)

Answer 1

Эта проблема хорошо известна как проблема смены монет. Пожалуйста, проверьте это и это для деталей. Также, если вы поменяете Google «изменение монеты» или «изменение монеты динамического программирования», вы получите много других полезных ресурсов.

Answer 2

Вот рекурсивное решение в Java:

// Usage: int[] denoms = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 };       
// System.out.println(ways(denoms, denoms.length, 200));
public static int ways(int denoms[], int index, int capacity) {
    if (capacity == 0) return 1;
    if (capacity < 0 || index <= 0 ) return 0;
    int withoutItem = ways(denoms, index - 1, capacity); 
    int withItem = ways(denoms, index, capacity - denoms[index - 1]); 
    return withoutItem + withItem;
}

Answer 3

Это похоже на раздел, за исключением того, что вы не используете все целые числа в 1:50.Это также похоже на проблему упаковки бина с небольшими отличиями:

• Википедия: Разделение (Теория чисел)
• Википедия: Проблема упаковки бина
• Wolfram Mathworld: Partiton

На самом деле, если подумать, это ILP , и, следовательно, NP-сложный.

Я бы предложил некоторый метод динамического программирования.По сути, вы определяете значение «остаток» и устанавливаете его в соответствии с вашей целью (скажем, 50).Затем на каждом шаге вы будете делать следующее:

1. Выясните, какая самая большая монета может поместиться в остатке
2. Подумайте, что произойдет, если вы (A) включитеэта монета или (B) не включали эту монету.
3. Для каждого сценария рекурсивно.

Так что, если остаток был 50, а самые большие монеты стоили 25 и 10, вы 'Разветвление d в два сценария:

1. Remainder = 25, Coinset = 1x25
2. Remainder = 50, Coinset = 0x25

Следующий шаг (для каждой ветви) может выглядеть следующим образом:

1-1. Remainder = 0,  Coinset = 2x25 <-- Note: Remainder=0 => Logged
1-2. Remainder = 25, Coinset = 1x25
2-1. Remainder = 40, Coinset = 0x25, 1x10
2-2. Remainder = 50, Coinset = 0x25, 0x10

Каждая ветвь будет разделена на две ветви, если:

• остаток был 0 (в этом случае вы записали бы его)
• остаток был меньше самой маленькой монеты (в этом случае вы бы выбросили его)
• больше не былоосталось монет (в этом случае вы бы сбросили его, так как остаток! = 0)

Answer 4

Если у вас есть монеты 15, 10, 6 и 2 цента, и вам нужно найти, сколько разных способов добраться до 50 вы можете

• посчитайте, сколько разных способов вам нужно достичь 50, используя только 10, 6 и 2
• посчитайте, сколько разных способов вам нужно достичь 50-15, используя только 10, 6 и 2
• посчитайте, сколько разных способов вам нужно достичь 50-15 * 2, используя только 10, 6 и 2
• посчитайте, сколько разных способов вам нужно достичь 50-15 * 3, используя только 10, 6 и 2
• Суммируйте все эти результаты, которые, конечно, различны (в первом я использовал не 15c монеты, во втором я использовал одну, в третьих два и в четвертой три).

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

Более того, вы также можете избежать повторения тех же вычислений, используя памятку, например, количество способов достижения 20 с использованием только [6, 2] не зависит от того, были ли достигнуты уже оплаченные 30 с использованием 15 + 15 или 10. + 10 + 10, поэтому результат меньшей задачи (20, [6, 2]) может храниться и использоваться повторно.

В Python реализация этой идеи следующая

cache = {}

def howmany(amount, coins):
    prob = tuple([amount] + coins) # Problem signature
    if prob in cache:
        return cache[prob] # We computed this before
    if amount == 0:
        return 1 # It's always possible to give an exact change of 0 cents
    if len(coins) == 1:
        if amount % coins[0] == 0:
            return 1 # We can match prescribed amount with this coin
        else:
            return 0 # It's impossible
    total = 0
    n = 0
    while n * coins[0] <= amount:
        total += howmany(amount - n * coins[0], coins[1:])
        n += 1
    cache[prob] = total # Store in cache to avoid repeating this computation
    return total

print howmany(50, [15, 10, 6, 2])

Answer 5

Для такого небольшого количества монет вы можете написать простое решение грубой силы.

Примерно так:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> v;

int solve(int total, int * coins, int lastI)
{
    if (total == 50) 
    {
        for (int i = 0; i < v.size(); i++)
        {
            cout << v.at(i) << ' ';
        }
        cout << "\n";
        return 1;
    }

    if (total > 50) return 0;

    int sum = 0;

    for (int i = lastI; i < 6; i++)
    {
        v.push_back(coins[i]);
        sum += solve(total + coins[i], coins, i); 
        v.pop_back();
    }

    return sum;
}


int main()
{
    int coins[6] = {2, 4, 6, 10, 15, 50};
    cout << solve(0, coins, 0) << endl;
}

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

Это очень известная проблема, поэтому попробуйте прочитать о лучших решениях, предоставленных другими.

Answer 6

Что касается второй части вашего вопроса, предположим, что у вас есть эта строка в файле coins.txt:

#include <fstream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::ifstream coins_file("coins.txt");
    std::vector<int> coins;
    std::copy(std::istream_iterator<int>(coins_file),
              std::istream_iterator<int>(),
              std::back_inserter(coins));
}

Теперь вектор coins будет содержать возможные значения монет.

Answer 7

Другая версия Python:

def change(coins, money):
    return (
        change(coins[:-1], money) +
        change(coins, money - coins[-1])
        if money > 0 and coins
        else money == 0
    )

Answer 8

Рекурсивное решение на основе gorithist.com ресурса в Scala:

def countChange(money: Int, coins: List[Int]): Int = {
    if (money < 0 || coins.isEmpty) 0
    else if (money == 0) 1
    else countChange(money, coins.tail) + countChange(money - coins.head, coins)
}

Answer 9

Алгоритм - это процедура для решения проблемы, она не должна быть написана на каком-либо конкретном языке.

Сначала отработайте входные данные:

typedef int CoinValue;

set<CoinValue> coinTypes;
int value;

и выходы:

set< map<CoinValue, int> > results;

Решите для самого простого случая, о котором вы можете подумать:

coinTypes = { 1 }; // only one type of coin worth 1 cent
value = 51;

результат должен быть:

results = { [1 : 51] }; // only one solution, 51 - 1 cent coins

Как бы вы решили вышеуказанное?

Как насчет этого:

coinTypes = { 2 };
value = 51;

results = { }; // there is no solution

что по этому поводу?

coinTypes = { 1, 2 };
value = { 4 };

results = { [2: 2], [2: 1, 1: 2], [1: 4] }; // the order I put the solutions in is a hint to how to do the algorithm.

Answer 10

Сортировка списка в обратном порядке: [15 10 6 4 2]

Теперь решение на 50 кт может содержать 15 кт или нет.Таким образом, число решений - это количество решений для 50 кар, используя [10 6 4 2] (больше не считая монет 15 кар) плюс количество решений для 35 кар (= 50 кар - 15 кар), используя [15 10 6 4 2].Повторите процесс для обеих подзадач.