⇤ ← Версия 1 от 2019-08-01 11:11:57
2305
Комментарий:
|
← Версия 2 от 2019-08-01 12:45:49 ⇥
2301
|
Удаления помечены так. | Добавления помечены так. |
Строка 12: | Строка 12: |
1. Надо: суммарный объём | 1. Надо: суммарный объём |
Строка 20: | Строка 20: |
'''Набить''' объём набором вещей: | '''Набить''' объём набором вещей: |
Строка 38: | Строка 38: |
== Многофакторнаый вариант == | == Многофакторный вариант == |
Задача о рюкзаке
Опыт по реконструкции решения задачи коммивояжёра «с нуля», без чтения сторонних ресурсов и формального применения линейного программирования (на самом деле, конечно, ЛП тут должно возникнуть).
TODO пока только план
Постановка простой задачи
- Рюкзак: объём
- Вещи: объём, стоимость
- Надо: суммарный объём
- Ценность
- цена вещи за 1 единицу объёма
Решение
Рекурсивная идея. Вещи отсортированы по убыванию ценности.
Набить объём набором вещей:
(отсечение) если попытка дозаполнить объём частями самой ценной на данном наборе вещи не превышают максимума
- Сразу вернуть меньшее число
- Набить экземплярами самой ценной вещи, пока можно
Оставшийся объём рекурсивно набить набором без самой ценной вещи
- Просуммировать стоимость, запомнить максимум
- Выбросить все вещи из «оставшегося объёма»
- Если есть ещё вещи (это самые ценные)
- Выбросить одну и перейти к п. 2
Простая задача с лимитами
- Количество вещей
- По идее, изменения в алгоритме не будет (п. 2)
- Вещи одинаковой ценности, но разного объёма
- По идее, достаточно упорядочить по (ценность, объём)
Решение задачи с лимитами
Многофакторный вариант
TODO ограничения по объёму и весу; общий вид; подходы к решению