Задача о рюкзаке

Опыт по реконструкции решения задачи коммивояжёра «с нуля», без чтения сторонних ресурсов и формального применения линейного программирования (на самом деле, конечно, ЛП тут должно возникнуть).


TODO пока только план

Постановка простой задачи

  1. Рюкзак: объём
  2. Вещи: объём, стоимость
  3. Надо: суммарный объём
  4. Ценность
    цена вещи за 1 единицу объёма

Решение

Рекурсивная идея. Вещи отсортированы по убыванию ценности.

Набить объём набором вещей:

  1. (отсечение) если попытка дозаполнить объём частями самой ценной на данном наборе вещи не превышают максимума

    1. Сразу вернуть меньшее число
  2. Набить экземплярами самой ценной вещи, пока можно
  3. Оставшийся объём рекурсивно набить набором без самой ценной вещи

  4. Просуммировать стоимость, запомнить максимум
  5. Выбросить все вещи из «оставшегося объёма»
  6. Если есть ещё вещи (это самые ценные)
    1. Выбросить одну и перейти к п. 2

Простая задача с лимитами

  1. Количество вещей
    1. По идее, изменения в алгоритме не будет (п. 2)
  2. Вещи одинаковой ценности, но разного объёма
    1. По идее, достаточно упорядочить по (ценность, объём)

Решение задачи с лимитами

Многофакторный вариант

TODO ограничения по объёму и весу; общий вид; подходы к решению

FrBrGeorge/BackpackProblem (последним исправлял пользователь FrBrGeorge 2019-08-01 12:45:49)