Информатика · объяснение и практика

Почему в задаче о рюкзаке предмет нельзя использовать дважды незаметно

Собираем набор приборов в рюкзак и показываем, почему направление обновления одномерной таблицы отличает выбор 0/1 от неограниченных повторов.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Методы алгоритмов: углубление · Учебная карта

Главная мысль

В рюкзаке 0/1 каждый предмет разрешено взять не более одного раза. Состояние должно учитывать и доступные предметы, и вместимость. При сжатии таблицы до одной строки вместимости перебирают вниз, чтобы текущий предмет не использовался повторно.

Что именно мы выбираем

Для экспедиции есть фонарь массой 3 и полезностью 8, датчик массой 4 и полезностью 9, блокнот массой 2 и полезностью 5. Вместимость равна 6. Масса здесь измеряется целыми условными единицами; полезности складываются, а каждый предмет существует в одном экземпляре.

Фонарь с блокнотом дают массу 5 и полезность 13. Датчик с блокнотом дают массу 6 и полезность 14 — это лучший допустимый набор. Фонарь с датчиком не помещаются. Выбирать только самый полезный предмет или только лучший показатель полезности на единицу массы недостаточно.

Пример

При вместимости 6 оптимум равен 14: датчик и блокнот.

Это задача о неделимых предметах. Нельзя отрезать часть датчика или положить второй блокнот, если такого экземпляра в условии нет.

Зачем состоянию номер предмета

Обозначим F(i,c) наибольшую полезность при вместимости c, когда доступны только первые i предметов. Для очередного предмета массы m и полезности v сравниваем отказ F(i−1,c) с выбором v+F(i−1,c−m), если c≥m. Обе ветви ссылаются на предыдущий набор доступных предметов.

Базовая строка без предметов содержит нули для любой неотрицательной вместимости. Это означает «можно оставить место свободным», а не «рюкзак обязательно заполнен точно». Для требования точной массы недостижимые состояния нужно отмечать отдельно: нулевой полезностью их подменять нельзя. Например, единственный предмет массы два вообще не заполняет вместимость три точно. При условии «не превышать три» тот же предмет допустим, поэтому формулировка задачи определяет даже начальные значения таблицы.

Как один проход случайно создаёт копии

Оставим только блокнот массы 2 с полезностью 5 и вместимость 4. Если обновлять одну строку слева направо, клетка 2 станет равна 5, а затем клетка 4 возьмёт уже обновлённую клетку 2 и станет 10. Получились два одинаковых блокнота вместо одного.

При движении справа налево клетка 4 читает старое значение клетки 2, ещё не затронутое текущим предметом. Поэтому максимум остаётся 5. Такое направление нужно для положительных целых масс в этой одномерной схеме 0/1; при разрешённых неограниченных повторах обновление вверх, наоборот, может быть намеренным.

От чтения к действию

А теперь — вы

Есть один предмет массы 3 с полезностью 7. Вместимость 6, повторы запрещены. Каков максимум полезности?

Частые вопросы

Достаточно ли вывести только максимальную полезность?

Если нужен сам набор, сохраняют решения переходов или восстанавливают их по полной таблице. Одно итоговое число не сообщает, какие предметы выбраны.

Почему целые массы имеют значение?

Таблица индексируется вместимостью. Для произвольных дробных масс сначала нужна обоснованная дискретизация или другой метод; округление способно изменить допустимые наборы.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться