Как определить, достаточно ли жадного алгоритма для нахождения минимального обмена монет? - PullRequest
Новая
       45

Как определить, достаточно ли жадного алгоритма для нахождения минимального обмена монет?

6 голосов
/ 17 мая 2011

Задача минимальная смена монет является NP-полной задачей, но для некоторых наборов монет работает жадный алгоритм (сначала выберите самые крупные номиналы).Учитывая набор целых чисел, обозначающих значения монет, какой самый быстрый алгоритм определяет, достаточен ли жадный алгоритм или нет?Одним из очевидных способов является создание вашего динамического программного решения до наибольшего номинала и посмотреть для каждого, дает ли оно лучшее решение, чем жадный путь.Но есть ли более быстрый «математический способ» его обнаружения?

Ответы [ 3 ]

2 голосов
/ 06 марта 2013

Недавно я предложил 1 решение, которое, казалось бы, показывало, что если заданные 2 условия выполнены, жадный алгоритм даст оптимальное решение.

а) ДС (все наименования, кроме 1) = 2-й наименьший номинал.

b) Сумма любых двух последовательных номиналов должна быть меньше, чем 3-й последовательный номинал.

Например, с2 + с3 <с4. </p>

(где c1 = 1; c2, c3, c4 - номиналы монет в порядке возрастания).

Я понимаю, что это не полное решение. Тем не менее, я считаю, что если эти 2 условия будут выполнены, жадный алгоритм даст оптимальное решение.

0 голосов
/ 04 января 2013

Жадный алгоритм будет работать, если следующий выбор дает целевое количество: (могут быть более сложные форматы, которые будут работать, но это просто и линейно проверить)

Пусть 1 представляет выбранный.Набор из наибольшего номинала будет выглядеть следующим образом: 

11...1100...00100...00

То есть ноль или более выбирается из наибольшего, и выбирается один другой элемент.

Почему это оптимально,просто доказатьПусть C = s элементов, выбранных из самых больших, тогда мы знаем, что C производит наибольшую возможную сумму для любого s или менее элементов, так как, если бы вы должны были заменить любой элемент в C, вы должны были бы сделать это с более низкимценный элемент, так как самые большие элементы уже выбраны (и удаление также, очевидно, уменьшит стоимость).Так как C производит значение меньше цели (из-за того, что требуется еще один элемент), нам нужен по крайней мере еще один элемент для достижения цели, поэтому минимальное количество элементов, необходимых для достижения цели, составляет s + 1, чтозавершает доказательство.

Вам нужно O (n), чтобы оценить это, и это можно сделать следующим образом: (в Java) 

int[] sortedCoins = ...;
int sum = 0, selectionCount = 0, i = 0;
for (; i < sortedCoins.length; i++)
{
  sum += sortedCoins[i];
  if (sum >= target) break;
  selectionCount++;
}
sum -= sortedCoins[i]; // we added the element to push us over, so remove it again
for (; i < sortedCoins.length; i++)
{
  if (sum + sortedCoins[i] == target)
    return selectionCount+1;
}
return -1; // not found

О, и есть также тривиальный случай, когдаtarget = 0, что необходимо проверить, разрешено ли это.

Выше требуется целевая сумма. Если вы хотите проверить много целевых сумм, вы, вероятно, можете сгенерировать все возможные суммы указанным выше методом в O (n ^2) и иметь карту суммы к количеству и просто выполнить поиск, чтобы получить значение, если оно существует.

РЕДАКТИРОВАТЬ: Ветвь и граница

КакВ дополнение к вышесказанному и в качестве альтернативы DP, я предлагаю грубую силу, обработанную жадно с помощью ветвей и границ.Используя аргумент, аналогичный приведенному выше, вы знаете, что можете пропустить текущий путь, если значение bestCoins имеет значение и (currentSum + (bestCoins - currentCoins) * currentItem.value) < target.

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

Если все сделано правильно, вы сможете запустить его на короткое время, и если оно дойдет до завершения и у нас есть решение, у нас будет оптимальное решение, если нет, мы не потеряли слишком много времени и можем запустить другоеАлгоритм типа DP.

0 голосов
/ 01 июля 2011

Жадное решение работает только для определенных номиналов относительно определенной суммы, для которой необходимо внести изменение.

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

Пример: рассмотрим монетность = [2, 5], а сумма, подлежащая изменению, равна 16. Сначала жадныйРешение, естественно, сначала ищет наибольшие номиналы, [5, 5, 5], а затем застряло на 1. Шаг возврата возвращает другое решение [5, 5, 2, 2, 2].

...