Почему алгоритм с алчными монетами не работает для некоторых наборов монет?

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

Но для некоторых наборов монет есть суммы, для которых жадный алгоритм терпит неудачу. Например, для набора {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