жадные алгоритмы

Question

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

Внутри книги есть различные проблемы, но у меня возникли проблемы с пониманием и ответом на конкретный вопрос.

Во-первых, это проблема, которая (я только что скопировал текст).

существует набор из n объектов размеров {x1; x2; ..... xn} и bin с емкостью B. Все это положительные целые числа. Попробуйте найти подмножество этих объектов , чтобы их общий размер был меньше или равен B, но как можно ближе к B.

Все объекты 1-мерные. Например, если объекты имеют размеры 4, 7, 10, 12, 15 и B = 20, тогда мы должны выбрать 4 и 15 с общим размером 19 (или, что то же самое, 7 и 12). Для каждого из следующих жадных алгоритмов покажите, что они не являются оптимальными, создав встречный пример. постарайтесь сделать ваши примеры настолько плохими, насколько сможете, где «плохость» измеряется соотношением между оптимальными и жадными решениями. Таким образом, если наилучшее решение имеет значение 10, а жадность решения - значение 5, то отношение равно 2.

Как это сделать для следующего?

1) Всегда выбирайте объект с наибольшим размером, чтобы общий размер этого и всех других объектов, уже выбранных, не превышал B. Повторите это для остальных объектов.

Answer 1

Пусть следующий пример задачи:

У вас есть ящик размером 2n, один элемент размером n+1, а остальные имеют размер n.

Легко видеть, что оптимальным является 2 элемента размера n, в то время как жадные вы получите один элемент размера n+1.

Поскольку это верно для каждого n, оно фактически дает вам желаемое соотношение, по крайней мере, с использованием этого жадного подхода 2.

Answer 2

Это похоже на проблему с Knapsack 0-1, где каждый элемент имеет разный размер, но одно и то же значение, что означает, что ни один элемент не имеет никакого предпочтения быть помещенным в ящик, отличный от его размера. В вашем коде вам необходимо изучить каждый элемент и рассчитать максимальный общий размер, который приводит к тому, что он помещает его в корзину, не превышая емкость контейнера.