Укладка рюкзака для похода

Сентябрь 8, 2022

Главная
Алгебра
Укладка рюкзака для похода

Содержание

2. Исходный набор: В последней колонке указан суммарный вес Σa всех предметов и их суммарная стоимость Σb.
3. Набор с указанием ценности d: Он заключается в вычислении для каждой пары ценности d=a/b, по которой
4. Отсортированный по d набор
5. Попробуем найти решение при S=60. Первые пять предметов дадут нам Σa=38, Σb=128. Следующий предмет не помещается.
6. !
7. Если мы заменим предмет 23-27 на 26-30,
8. Рассмотрим предельный случай. У нас есть два предмета, которые по одиночке помещаются в рюкзак, вместе же
9. Для того же S=60 Σa=55, Σb=143. Мы сразу приходим к оптимальному решению. Таким образом решается задача
11. Скачать презентацию

Слайд 2

Исходный набор:
В последней колонке указан суммарный вес Σa всех предметов и

их суммарная стоимость Σb. Задаваемое S (грузоподъемность) не должна превышать Σa, иначе решение тривиально — мы можем унести все. Учитывая эти ограничения, с помощью суммарной стоимости Σb мы можем оценить, насколько суммарная стоимость полученного решения отличается от абсолютного максимума.

Слайд 3

Набор с указанием ценности d:
Он заключается в вычислении для каждой пары

ценности d=a/b, по которой пары сортируются и затем отбираются.

Слайд 4

Отсортированный по d набор

Слайд 5

Попробуем найти решение при S=60.
Первые пять предметов дадут нам Σa=38, Σb=128.

Следующий предмет не помещается. С ним Σa=64. Дыра, оставшаяся после укладки первых пяти предметов получилась размером: 60-38=22. Если просмотреть набор до конца, находится еще один предмет, который в эту дыру помещается.

Слайд 6

!

Слайд 7

Если мы заменим предмет 23-27 на 26-30,

Слайд 8

Рассмотрим предельный случай. У нас есть два предмета, которые по одиночке

помещаются в рюкзак, вместе же нет. Естественным решением будет взять более дорогой предмет, несмотря на его больший вес. Очевидно, цена укладываемого предмета имеет более высокий приоритет, чем вес.
Небольшая переоценка ценности d позволяет сместить приоритет в нужную нам сторону.
Вместо простого отношения d=b/a, возьмем d=b2/a и по-прежнему отсортируем по d.

Слайд 9