Задача о рюкзаке
Опыт по реконструкции решения задачи коммивояжёра «с нуля», без чтения сторонних ресурсов и формального применения линейного программирования (на самом деле, конечно, ЛП тут должно возникнуть).
TODO пока только план
Постановка простой задачи
- Рюкзак: объём
- Вещи: объём, стоимость
- Надо: суммарный объём
- Ценность
- цена вещи за 1 единицу объёма
Решение
Рекурсивная идея. Вещи отсортированы по убыванию ценности.
Набить объём набором вещей:
(отсечение) если попытка дозаполнить объём частями самой ценной на данном наборе вещи не превышают максимума
- Сразу вернуть меньшее число
- Набить экземплярами самой ценной вещи, пока можно
Оставшийся объём рекурсивно набить набором без самой ценной вещи
- Просуммировать стоимость, запомнить максимум
- Выбросить все вещи из «оставшегося объёма»
- Если есть ещё вещи (это самые ценные)
- Выбросить одну и перейти к п. 2
Простая задача с лимитами
- Количество вещей
- По идее, изменения в алгоритме не будет (п. 2)
- Вещи одинаковой ценности, но разного объёма
- По идее, достаточно упорядочить по (ценность, объём)
Решение задачи с лимитами
Многофакторный вариант
TODO ограничения по объёму и весу; общий вид; подходы к решению