Слайд 2
![Исходный набор: В последней колонке указан суммарный вес Σa всех](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/239479/slide-1.jpg)
Исходный набор:
В последней колонке указан суммарный вес Σa всех предметов и
их суммарная стоимость Σb. Задаваемое S (грузоподъемность) не должна превышать Σa, иначе решение тривиально — мы можем унести все. Учитывая эти ограничения, с помощью суммарной стоимости Σb мы можем оценить, насколько суммарная стоимость полученного решения отличается от абсолютного максимума.
Слайд 3
![Набор с указанием ценности d: Он заключается в вычислении для](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/239479/slide-2.jpg)
Набор с указанием ценности d:
Он заключается в вычислении для каждой пары
ценности d=a/b, по которой пары сортируются и затем отбираются.
Слайд 4
![Отсортированный по d набор](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/239479/slide-3.jpg)
Отсортированный по d набор
Слайд 5
![Попробуем найти решение при S=60. Первые пять предметов дадут нам](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/239479/slide-4.jpg)
Попробуем найти решение при S=60.
Первые пять предметов дадут нам Σa=38, Σb=128.
Следующий предмет не помещается. С ним Σa=64.
Дыра, оставшаяся после укладки первых пяти предметов получилась размером: 60-38=22. Если просмотреть набор до конца, находится еще один предмет, который в эту дыру помещается.
Слайд 6
![!](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/239479/slide-5.jpg)
Слайд 7
![Если мы заменим предмет 23-27 на 26-30,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/239479/slide-6.jpg)
Если мы заменим предмет 23-27 на 26-30,
Слайд 8
![Рассмотрим предельный случай. У нас есть два предмета, которые по](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/239479/slide-7.jpg)
Рассмотрим предельный случай. У нас есть два предмета, которые по одиночке
помещаются в рюкзак, вместе же нет. Естественным решением будет взять более дорогой предмет, несмотря на его больший вес. Очевидно, цена укладываемого предмета имеет более высокий приоритет, чем вес.
Небольшая переоценка ценности d позволяет сместить приоритет в нужную нам сторону.
Вместо простого отношения d=b/a, возьмем d=b2/a и по-прежнему отсортируем по d.
Слайд 9
![Для того же S=60 Σa=55, Σb=143. Мы сразу приходим к](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/239479/slide-8.jpg)
Для того же S=60
Σa=55, Σb=143. Мы сразу приходим к оптимальному решению.
Таким
образом решается задача укладки рюкзака.