Алгоритм возможных сумм (пере), выплачиваемых по определенной цене, исходя из номиналов
В текущем проекте люди могут заказать товары, доставленные на дом, и выбрать «оплатить при доставке» в качестве варианта оплаты. Чтобы убедиться, что у доставщика достаточно изменений, клиентов просят ввести сумму, которую они будут платить (например, доставка 48,13, они заплатят 60, - (3 * 20, -)). Теперь, если бы это зависело от меня, я бы сделал это свободным полем, но, по-видимому, высшие должностные лица решили, что это должен быть выбор, основанный на доступных деноминациях, без предоставления сумм, которые привели бы к набору деноминаций, который мог бы быть меньшим.
Пример:
denominations = [1,2,5,10,20,50]
price = 78.12
possibilities:
79 (multitude of options),
80 (e.g. 4*20)
90 (e.g. 50+2*20)
100 (2*50)
Это международный, поэтому деноминации могут измениться, и алгоритм должен быть основан на этом списке.
Ближайшее, что мне кажется, работает, так это:
for all denominations in reversed order (large=>small)
add ceil(price/denomination) * denomination to possibles
baseprice = floor(price/denomination) * denomination;
for all smaller denominations as subdenomination in reversed order
add baseprice + (ceil((price - baseprice) / subdenomination) * subdenomination) to possibles
end for
end for
remove doubles
sort
Является ли , похоже, работать, но это возникло после дикой попытки всех видов компактных алгоритмов, и я не может защитить , почему это работает, что может привести к тому, что некоторые крайние случаи / новые страны получат неправильные варианты, и это приведет к серьезным удвоениям
.Поскольку это, вероятно, не новая проблема, и Google et al. не мог предоставить мне ответ, за исключением загрузки страниц, вычисляющих, как сделать точное изменение, я подумал, что задам вопрос: вы уже решили эту проблему раньше? Какой алгоритм? Есть ли доказательства, что это всегда будет работать?
2 ответа
Это приложение жадного алгоритма http://mathworld.wolfram.com/GreedyAlgorithm.html (алгоритм, используемый для рекурсивного построения набора объектов из минимально возможных составляющих частей)
Псевдокод
list={1,2,5,10,20,50,100} (*ordered *)
while list not null
found_answer = false
p = ceil(price) (* assume integer denominations *)
while not found_answer
find_greedy (p, list) (*algorithm in the reference above*)
p++
remove(first(list))
РЕДАКТИРОВАТЬ> некоторые итерации - ерунда>
list={1,2,5,10,20,50,100} (*ordered *)
p = ceil(price) (* assume integer denominations *)
while list not null
found_answer = false
while not found_answer
find_greedy (p, list) (*algorithm in the reference above*)
p++
remove(first(list))
РЕДАКТИРОВАТЬ>
Я обнаружил улучшение алгоритма Жадности Пирсона. Его O (N ^ 3 log Z), где N - количество номиналов, а Z - наибольшая купюра в наборе.
Вы можете найти его в http://library.wolfram.com/infocenter/MathSource/5187/
Вы можете сгенерировать в базе данных все возможные наборы комбинаций выплаченных монет и бумаги (я не очень хорошо говорю по-английски), и каждая строка содержит сумму этой комбинации.
Имея эту базу данных, вы можете просто получить все возможные переплаты одним запросом,
WHERE sum >= cost and sum <= cost + epsilon
Несколько слов об эпсилон, хм .. вы можете назначить это из стоимости? Может быть, 10% от стоимости + 10 баксов?:
WHERE sum >= cost and sum <= cost * 1.10 + 10
В структуре таблицы должно быть количество столбцов, представляющих количество монет и тип бумаги. В значениях каждого столбца указано количество вхождений данного типа оплаченного товара.
Это не оптимальное и быстрое решение данной проблемы, но его легко и просто реализовать. Я думаю о лучшем решении этого.
Другой способ: от стоимости до стоимости + эпсилон и для каждого значения вычислить минимально возможное количество оплачиваемых предметов для каждого. У меня есть алгоритм. Вы можете сделать это с помощью этого алгоритма, но он находится в C ++:
int R[10000];
sort(C, C + coins, cmp);
R[0]=0;
for(int i=1; i <= coins_weight; i++)
{
R[i] = 1000000;
for (int j=0; j < coins; j++)
{
if((C[j].weight <= i) && ((C[j].value + R[i - C[j].weight]) < R[i]))
{
R[i] = C[j].value + R[i - C[j].weight];
}
}
}
return R[coins_weight];