Почему алгоритм с алчными монетами не работает для некоторых наборов монет?
Я понимаю, как работает жадный алгоритм для проблемы с изменением монет (выплачивается определенная сумма с минимально возможным количеством монет) - он всегда выбирает монету с наибольшим наименованием, не превышающую оставшуюся сумму, и что он всегда находит правильное решение для конкретных наборов монет.
Но для некоторых наборов монет есть суммы, для которых жадный алгоритм терпит неудачу. Например, для набора {1, 15, 25} и суммы 30, жадный алгоритм сначала выбирает 25, оставляя остаток из 5, а затем пять 1 с для всего шести монет. Но решение с минимальным количеством монет состоит в том, чтобы выбрать 15 дважды.
Какие условия должен выполнить набор монет, чтобы алчный алгоритм нашел минимальное решение для всех сумм?
Ответы
Ответ 1
Набор, который образует матроид (https://en.wikipedia.org/wiki/Matroid), может быть использован для решения проблемы с изменением монет, используя жадный подход. Короче говоря, матроид - упорядоченная пара
M = (S, l), удовлетворяющих следующим условиям:
- S - конечное непустое множество
- l - непустое семейство подмножеств S, называемое независимыми подмножествами, такое, что если B- > l
и A - подмножество B, то A → l
- Если A- > l, B- > l и | A | < | B |, то найдется некоторый элемент x- > B-A такой, что A U {x} → l
В нашем вопросе о смене монеты S представляет собой набор всех монет в порядке убывания порядка
Нам нужно достичь значения V минимальным количеством монет в S
В нашем случае l является независимым множеством, содержащим все подмножества такие, что для каждого подмножества выполняется следующее: суммирование значений в них равно <= V
Если наше множество является матроидом, то наш ответ является максимальным множеством A в l, в котором no x может быть дополнительно добавлено
Чтобы проверить, мы видим, обладают ли свойства матроида в множестве S = {25,15,1}, где V = 30
Теперь в l есть два подмножества:
A = {25} и B = {15,15}
Так как | A | < | B |, то найдется некоторый элемент x- > B-A такой, что A U {x} → l (согласно 3)
Итак, {25,15} должно принадлежать l, но его противоречие с 25 + 15 > 30
Итак, S не является матроидом, и поэтому жадный подход не будет работать на нем.
Ответ 2
Система монет является канонической, если количество монет, заданных при изменении жадным алгоритмом, оптимально для всех сумм.
В этой статье предлагается алгоритм O (n ^ 3) для определения того, является ли система монет канонической, где n - количество различных видов монет.
Для неканонической монетной системы существует количество c, для которого жадный алгоритм создает неоптимальное количество монет; c называется контрпримером. Система монет плотная, если ее самый маленький контрпример больше, чем самая большая одиночная монета.
Ответ 3
В любом случае, когда нет монеты, значение которой при добавлении к наименьшему наименованию ниже, чем в два раза меньше, чем у наименования, которое меньше его, работает жадный алгоритм.
то есть. {1,2,3} работает, потому что [1,3] и [2,2] добавляют к тому же значению однако {1, 15, 25} не работает, потому что (для изменения 30) 15 + 15 > 25 + 1
Ответ 4
Понятно, что любой набор монет такой, что если они отсортированы в порядке возрастания и у вас есть:
coin[0] = 1
coin[i+1] >= 2 * coin[i], for all i = 0 .. N-1 in coin[N]
Тогда будет работать жадный алгоритм с использованием таких монет.
В зависимости от диапазона, который вы запрашиваете, может быть более оптимальным (с точки зрения количества требуемых монет). Например, если вы рассматриваете диапазон (6..8), и у вас есть монеты < 6, 7, 8 > вместо < 1, 2, 4, 8 > .
Наиболее эффективное распределение монет, которое завершено над N +, равно равенству вышеуказанного набора правил, давая вам монеты 1, 2, 4, 8...; который просто является двоичным представлением любого числа. В некотором смысле разговор между базами - это жадный алгоритм сам по себе.
Доказательство неравенствa >= 2N представлено Макс Рабкиным в этом обсуждении:
http://olympiad.cs.uct.ac.za/old/camp0_2008/day1_camp0_2008_discussions.pdf
