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

В текущем проекте люди могут заказывать товары, доставленные к их двери, и выбирать "оплату при доставке" в качестве варианта оплаты. Чтобы убедиться, что у парцевания доставки достаточно изменений, клиентам предлагается ввести сумму, которую они будут платить (например, доставка 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. не мог предоставить мне ответ, за исключением загрузок страниц, подсчитывающих, как сделать точные изменения, я думал, что спрошу: вы решили эту проблему раньше? Какой алгоритм? Любое доказательство это всегда будет работать?

Ответы

Ответ 1

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

EDIT > некоторые итерации нонсенs > 

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/

Ответ 2

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

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

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

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

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

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

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

Другой способ: от cost до cost + epsilon и для каждого значения рассчитывать наименьшее возможное количество платных предметов для каждого. У меня есть алгоритм для этого. Вы можете сделать это с помощью этого алгоритма, но это в С++:

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];

Забастовкa >