- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Укладка рюкзака для похода презентация
Содержание
- 1. Укладка рюкзака для похода
- 2. Исходный набор: В последней колонке указан суммарный
- 3. Набор с указанием ценности d: Он заключается
- 4. Отсортированный по d набор
- 5. Попробуем найти решение при S=60. Первые пять
- 6. !
- 7. Если мы заменим предмет 23-27 на 26-30,
- 8. Рассмотрим предельный случай. У нас есть два
- 9. Для того же S=60 Σa=55, Σb=143. Мы
- 10. ??????
Исходный набор: В последней колонке указан суммарный вес Σa всех предметов и их суммарная стоимость Σb. Задаваемое S (грузоподъемность) не должна превышать Σa, иначе решение тривиально — мы можем унести все.
Слайд 2Исходный набор:
В последней колонке указан суммарный вес Σa всех предметов и
их суммарная стоимость Σb. Задаваемое S (грузоподъемность) не должна превышать Σa, иначе решение тривиально — мы можем унести все. Учитывая эти ограничения, с помощью суммарной стоимости Σb мы можем оценить, насколько суммарная стоимость полученного решения отличается от абсолютного максимума.
Слайд 3Набор с указанием ценности d:
Он заключается в вычислении для каждой пары
ценности d=a/b, по которой пары сортируются и затем отбираются.
Слайд 5Попробуем найти решение при S=60.
Первые пять предметов дадут нам Σa=38, Σb=128.
Следующий предмет не помещается. С ним Σa=64.
Дыра, оставшаяся после укладки первых пяти предметов получилась размером: 60-38=22. Если просмотреть набор до конца, находится еще один предмет, который в эту дыру помещается.
Слайд 8 Рассмотрим предельный случай. У нас есть два предмета, которые по одиночке
помещаются в рюкзак, вместе же нет. Естественным решением будет взять более дорогой предмет, несмотря на его больший вес. Очевидно, цена укладываемого предмета имеет более высокий приоритет, чем вес.
Небольшая переоценка ценности d позволяет сместить приоритет в нужную нам сторону.
Вместо простого отношения d=b/a, возьмем d=b2/a и по-прежнему отсортируем по d.
Небольшая переоценка ценности d позволяет сместить приоритет в нужную нам сторону.
Вместо простого отношения d=b/a, возьмем d=b2/a и по-прежнему отсортируем по d.
Слайд 9Для того же S=60
Σa=55, Σb=143. Мы сразу приходим к оптимальному решению.
Таким
образом решается задача укладки рюкзака.
