Обсуждение:Жадный алгоритм

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Алгоритмов по-моему не хватает. Насколько я знаю есть ещё алгоритмы Дейкстра, Флойда, и ещё какие-то. Я о них ничё не знаю, поэтому писать не буду.

1. Есть-то они есть, да вот "жадные" ли они????

2. Неплохо бы слово "жадный" в кавычки взять. А то сами по себе алгоритмы не бывают ни жадными, ни щедрыми, ни добрыми, ни злыми. 94.25.37.21 20:03, 12 июля 2009 (UTC)[ответить]

Примеры | Размен монет[править код]

В разделе про размен монет сказано, что, если сумма двух любых меньших номиналов всегда меньше или равна большему номиналу, то жадный алгоритм дает правильный ответ. Это неверно. Рассмотрим, например, номиналы 1, 10, 21 и попробуем разменять 30. Жадный алгоритм дает 1*21 + 9*1, т.е. 10 монет, при этом это можно сделать за 3 монеты: 3*10. --Metallo lom 21:20, 6 марта 2015 (UTC)[ответить]

  • Это верно подмечено, и ошибка тянется, наверное, с англовики, где вообще какое-то противоречие написано: In the US (and most other) coin systems, a greedy algorithm of picking the largest denomination of coin which is not greater than the remaining amount to be made will always produce the optimal result. This is not automatically the case, though: if the coin denominations were 1, 3 and 4, then to make 6, the greedy algorithm would choose three coins (4,1,1) whereas the optimal solution is two coins (3,3). РоманСузи 12:23, 7 марта 2015 (UTC)[ответить]