Алгоритм определения комбинаций монет
Недавно я столкнулся с подсказкой для алгоритма программирования, который я понятия не имел, что делать. Я никогда прежде не писал алгоритм, так что я новичок в этом.
Задача состоит в том, чтобы написать программу для определения всех возможных комбинаций монет для кассира, чтобы вернуть в виде изменений на основе стоимости монет и количества монет. Например, может существовать валюта с 4 монетами: 2 цента, 6 центов, 10 центов и 15 центов. Сколько существует комбинаций, равных 50 центам?
Я использую язык C++, хотя это не имеет большого значения.
редактировать: это более конкретный вопрос программирования, но как мне проанализировать строку в C++, чтобы получить значения монет? Они были даны в текстовом документе, как
4 2 6 10 15 50
(где числа в этом случае соответствуют примеру, который я дал)
13 ответов
Это похоже на раздел, за исключением того, что вы не используете все целые числа в 1:50. Это также похоже на проблему с упаковкой в мусорное ведро с небольшими отличиями:
- Википедия: Разделение (Теория чисел)
- Википедия: проблема с упаковкой в бен
- Wolfram Mathworld: Partiton
На самом деле, подумав об этом, это ILP, а значит и NP-hard.
Я бы предложил немного динамического программирования. По сути, вы бы определили значение "остаток" и установили его в соответствии с вашей целью (скажем, 50). Затем на каждом этапе вы будете делать следующее:
- Выясните, какая самая большая монета, которая может вписаться в остаток
- Подумайте, что произойдет, если вы (A) включите эту монету или (B) не включите эту монету.
- Для каждого сценария выполните рекурсию.
Таким образом, если остаток был 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)
Вот рекурсивное решение в 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;
}
Если у вас есть монеты 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])
Что касается второй части вашего вопроса, предположим, что у вас есть эта строка в файле 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 будет содержать возможные значения монет.
Для такого небольшого количества монет вы можете написать простое решение грубой силы.
Что-то вроде этого:
#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;
}
Очень грязное решение грубой силы, которое печатает все возможные комбинации.
Это очень известная проблема, поэтому попробуйте прочитать о лучших решениях, предоставленных другими.
В основном вам нужно решить следующее уравнение: 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 и затем начинать давать c все возможные значения в зависимости от текущего значение г и тд.
Рекурсивное решение на основе ресурса алгоритмист.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)
}
Алгоритм - это процедура для решения проблемы, она не должна быть написана на каком-либо конкретном языке.
Сначала отработайте входные данные:
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.
Один довольно тупой подход заключается в следующем. Вы строите отображение "монета со значением X используется Y раз", а затем перечисляете все возможные комбинации и выбираете только те, которые составляют желаемую сумму. Очевидно, что для каждого значения X вы должны проверить Y в диапазоне от 0 до желаемой суммы. Это будет довольно медленно, но решит вашу задачу.
Другая версия Python:
def change(coins, money):
return (
change(coins[:-1], money) +
change(coins, money - coins[-1])
if money > 0 and coins
else money == 0
)
Сортировать список в обратном порядке: [15 10 6 4 2]
Теперь решение за 50 кар может содержать 15 кар или нет. Таким образом, количество решений - это количество решений для 50 кар, используя [10 6 4 2] (больше не считая монет в 15 кар), плюс количество решений для 35 кар (=50 кар - 15 кар), используя [15 10 6 4 2], Повторите процесс для обеих подзадач.