Алгоритм возможных сумм (пере), выплачиваемых по определенной цене, исходя из номиналов - PullRequest
Новая
       21

Алгоритм возможных сумм (пере), выплачиваемых по определенной цене, исходя из номиналов

10 голосов
/ 05 июня 2010

В текущем проекте люди могут заказать товары, доставленные на дом, и выбрать «оплатить при доставке» в качестве варианта оплаты. Чтобы убедиться, что у доставщика достаточно изменений, клиентов просят ввести сумму, которую они будут платить (например, доставка 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 ]

2 голосов
/ 05 июня 2010

Применение алгоритма Жадности 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))

EDIT>

Я нашел улучшение благодаря алгоритму Жадности Пирсона. Это O (N ^ 3 log Z), где N - количество конфессий, а Z - наибольшая банкнота из множества.

Вы можете найти его в http://library.wolfram.com/infocenter/MathSource/5187/

0 голосов
/ 05 июня 2010

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

Имея эту базу данных, вы можете просто получить все возможные переплаты одним запросом, 

WHERE sum >= cost and sum <= cost + epsilon

Несколько слов о эпсилоне, хм .. вы можете назначить его по стоимости? Может быть, 10% от стоимости + 10 долларов?: 

WHERE sum >= cost and sum <= cost * 1.10 + 10

Структура таблицы должна иметь количество столбцов, представляющих количество монет и тип бумаги. Значение каждого столбца имеет количество вхождений этого типа оплаченного товара.

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

Другим способом можно от cost до cost + epsilon и для каждого значения рассчитать наименьшее возможное количество оплаченных предметов для каждого. У меня есть алгоритм для этого. Вы можете сделать это с помощью этого алгоритма, но это в 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];

...