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

Ответ 1

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

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

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

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

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

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

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)

Ответ 2

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

Ответ 3

Здесь рекурсивное решение в 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;
}

Ответ 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 монеты, во втором я использовал один, в третьем и четвертом).

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

Кроме того, вы также можете избежать повторения одного и того же вычисления с помощью memoization, например, количество способов достижения 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 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 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])

Ответ 5

Что касается второй части вашего вопроса, предположим, что у вас есть эта строка в файле 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 будет содержать возможные значения монет.

Ответ 6

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

Что-то вроде этого:

#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;
}

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

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

Ответ 7

Один довольно немой подход заключается в следующем. Вы создаете сопоставление "монета со значением X используется Y раз", а затем перечисляете все возможные комбинации и выбираете только те, которые суммируют желаемую сумму. Очевидно, что для каждого значения X вы должны проверить Y от 0 до желаемой суммы. Это будет довольно медленным, но решит вашу задачу.

Ответ 8

Он очень похож на проблема с рюкзаком

Ответ 9

Вы в основном должны решить следующее уравнение: 50 = a * 4 + b * 6 + c * 10 + d * 15, где неизвестные - a, b, c, d. Вы можете вычислить, например, d = (50 - a * 4 - b * 6 - c * 10)/15 и так далее для каждой переменной. Затем вы начинаете давать d все возможные значения (вы должны начать с того, который имеет наименьшие возможные значения, здесь d): 0,1,2,3,4, а затем начать давать все возможные значения в зависимости от текущего значение d и т.д.

Ответ 10

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

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

Ответ 11

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

Сначала выполните входы:

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.

Ответ 12

Рекурсивное решение на основе algorithmist.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)
}

Ответ 13

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

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