Минимум количества монет, которые меняют руки

У вас есть набор монет 5 ¢, 10 ¢, 20 ¢, 50 ¢, 1 $, 2 $ и ограниченное количество каждого номинала. Когда вы платите за определенную сумму, есть две возможности: вы платите правильную сумму или платите больше, чем нужно, и получаете правильное изменение от клерка. Как вы можете свести к минимуму количество монет, которые меняют руки (т. Е. Свести к минимуму количество монет, которые вы даете, а также количество возвращенных монет). Предположим, что сумма всегда выплачивается, а клерк имеет бесконечное количество монет, плюс он всегда выбирает наиболее эффективные способы вернуть изменения.Минимум количества монет, которые меняют руки

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

Для полного описания проблемы: UVA Online Judge

источник

2013-03-06 Minh Pham

Это интересное упражнение, но какие проблемы вы имеете с этим? Что вы пробовали? Где вы застряли? Где ваш код? – John

Спасибо, я отредактировал свое описание. –

Для этого конкретного набора монет работает жадный алгоритм (попробуйте доказать это). В общем, это сложнее. – us2012

Минимизация количества монет, что сумма к данной сумме является версией Knapsack Problem.

Ваша проблема заключается в том, чтобы свести к минимуму coins(S1) + coins(S2) (вы к клерку + клерку к вам), где S1 - S2 = S (сумма, которую вы должны платить). Итак, вы хотите, чтобы решить эту проблему рюкзака для всех значений изменения между S и Smax (знать все значения coins(x)), а затем решить:

min coins(S1) + coins(S2) 
under constraints 
    S1 - S2 = S 
    S1 in [S, Smax]

Это может быть решено путем простого перечислением (тест на каждое возможное значение для S1).

Проблема заключается в определении значения Smax.

Я не уверен в этом, но я думаю, что, потому что ваша самая большая монета 2 $, если вы даете клерка нечто большее, чем S + 2 $ вы не будете иметь никаких менее монет перетекает. Поэтому я предполагаю, что Smax = S + 2$, но я приглашаю вас немного подумать.

источник

2013-03-06 16:23:20 alestanis

Используя ваши обозначения: если S1> S + 2, то клерк вернет вам монету в 2 доллара, так как его лучшим выбором является жадный алгоритм из-за множества монет. Таким образом, есть лучшее решение, которое не должно давать эту монету в размере 2 долларов клерку. ПРЕДУПРЕЖДЕНИЕ: это не относится к любому набору монет. Пример: если у вас есть $ 5 и $ 7 монет, и вы хотите заплатить $ 16. В этом случае Smax = S + maxcoin = 16 + 5 = 21, но S1> 21. S1 = 30 (6 x $ 5), S2 = 14 (2 x $ 7). –

Я недавно решил эту проблему на my blog. Вот концовка, но вы должны будете прочитать всю запись в блоге для этого, чтобы понять:

(define (floupia price coins) 
    (if (positive? (modulo price (apply gcd coins))) 
     (error 'floupia "infeasible") 
     (let ((coins (append coins (map negate coins)))) 
     (let loop ((n 1)) 
      (let ((xs (filter (lambda (xs) (= (sum xs) price)) 
          (combinations-with-replacement n coins)))) 
      (if (null? xs) (loop (+ n 1)) xs))))))

Основная идея заключается в том, чтобы сначала увидеть, если одна монета может оплатить счет, а затем две монеты, а затем три, и т. д., останавливаясь, когда вы найдете наименьшее решение. На каждом шаге рассмотрите все возможные комбинации всех монет с заменой, чтобы увидеть, есть ли решение, рассматривая изменение, полученное как отрицательное монеты. Например, с монетами номиналов 1, 3, 7, 31 и 153 и целевой ценой 17 существует 5-монетное решение, которое предполагает оплату трех 7-монет и получение одиночных 1-монет и 3-монет в изменении, но более эффективным решением является выплата одной 31-монеты и получение двух 7-монет в изменении.

источник

2013-03-06 18:27:59 user448810

Я не уверен, о чем вы говорите: останавливаясь, когда найдете самое маленькое решение. Если у вас есть 2 монеты: 1 и 100, и вы хотите заплатить 5. Есть решение, давая одну 100 монет и получая 95 1 обратно. Но есть лучше, что дает 5 единиц. Лучшее решение - не обязательно то, в котором вы даете меньше монет. –

Количество монет - n в цикле выше - начинается с 1 и увеличивается на каждом шаге по петле. В вашем примере n начинается с 1, не существует допустимого решения, поэтому n увеличивается до 2, нет приемлемого решения и т. Д., Пока n не достигнет 5 и не будет найдено решение заплатить пять 1-монет, когда вы остановитесь , На каждом шаге генерируются все возможные комбинации монет, с заменой, и каждый суммируется, чтобы увидеть, является ли это целью. См. Ссылку на запись в блоге выше для полного объяснения. – user448810

Я не согласен. При n = 1 существует решение: вы даете 100 монет. –

Это NP-полная проблема с типом, который обычно решается с помощью эвристического поиска. Соответствующая эвристика состоит в том, чтобы сначала попробовать более крупные наименования.

источник

2013-03-06 20:05:34

Минимум количества монет, которые меняют руки

ответ

Смежные вопросы