- Заполняется
- Читается
- Ответ
Задача о рюкзаке
Унести можно лишь ограниченный вес, а у каждого предмета есть вес и стоимость. Какие предметы взять, чтобы унести как можно больше ценного? Перебор всех комбинаций удваивает работу с каждым новым предметом. Таблица, где строки — предметы, а столбцы — вместимости, находит лучший набор клетка за клеткой. Нажмите на предмет, чтобы положить его в рюкзак, и нажмите на него еще раз (в рюкзаке или на полке), чтобы вынуть. Рюкзак заполняется по весу, а плитки показывают, сколько долларов вы уложили по сравнению с наилучшим возможным результатом. Нажмите «Лучшая укладка», чтобы увидеть лучший рюкзак. На панели можно менять килограммы и доллары предметов, добавлять и удалять предметы и задавать вместимость рюкзака. Вид «Таблица» показывает, как динамическое программирование находит лучший рюкзак: нажмите «Пуск», чтобы смотреть, как заполняется таблица, или «Шаг» и «Назад», чтобы двигаться по одному шагу, а чтобы перейти в любое место, перетащите ползунок шагов. Каждая строка добавляет один предмет, каждый столбец — это вместимость в килограммах, а в каждой клетке — наибольшее число долларов, которое помещается. Когда таблица выбрана, клавиши со стрелками делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.
Как это работает
- Нажимайте на коробки, чтобы уложить их в рюкзак, и смотрите, как он заполняется по весу в килограммах.
- Попробуйте набрать наибольшую возможную стоимость в долларах или нажмите «Лучшая укладка», чтобы увидеть лучший рюкзак.
- Откройте вид «Таблица» и нажмите «Пуск», чтобы увидеть, как каждая ячейка выбирает между тем, чтобы взять предмет или оставить его.
Как работает таблица
Каждая строка добавляет один предмет, а каждый столбец — это вместимость от 0 до вместимости рюкзака. Клетка хранит наибольшую стоимость, которая помещается в эту вместимость, если использовать предметы до ее строки включительно. Без нового предмета это клетка сверху. С ним, если он помещается, это стоимость предмета плюс лучшая стоимость для оставшегося веса, которая находится в строке выше, левее на вес предмета. Клетка хранит большее из двух. Первая строка, без предметов, состоит из одних нулей.
Обратный ход: какие предметы взяты
Правая нижняя клетка — это наибольшая стоимость. Чтобы найти предметы, начните с нее и сравните ее с клеткой сверху: если они равны, последний предмет не понадобился; если она больше, предмет в рюкзаке, поэтому вычтите его вес и перейдите в этот столбец. Каждый раз поднимайтесь на одну строку, пока не дойдете до первой. Приложение показывает этот обратный ход оранжевым и перечисляет уложенные предметы под таблицей.
Часто задаваемые вопросы
Что означает 0/1 в задаче о рюкзаке 0/1?
Каждый предмет кладется один раз или не кладется вовсе — никогда частично и никогда дважды. Если бы предметы можно было делить, как крупу, оптимально было бы класть сначала то, что дороже всего за единицу веса; это дробная (непрерывная) задача о рюкзаке.
Почему бы не класть сначала самое ценное за единицу веса?
Потому что целые предметы могут оставлять пустоты. При вместимости 7 и предметах весом 1, 3, 4 и 5 стоимостью 1, 4, 5 и 7 самое ценное за единицу веса — предмет весом 5, и после него остается место только для предмета весом 1, всего 8. А предметы весом 3 и 4 вместе стоят 9.
Насколько быстр алгоритм для задачи о рюкзаке?
В таблице (число предметов + 1) · (вместимость + 1) клеток, и каждая заполняется за один шаг. Это быстро при небольшой вместимости, но вместимость может быть огромным числом, поэтому в общем случае задача NP-трудна; табличный метод называют псевдополиномиальным.
Можно ли положить один и тот же предмет дважды?
Здесь нельзя. В неограниченной задаче о рюкзаке каждый предмет можно брать сколько угодно раз; тогда таблица читает клетку слева в той же строке, а не в строке выше, как в приложении о размене монет.
Отправляются ли куда-нибудь данные?
Нет. Все вычисляется в вашем браузере, а ваши последние настройки остаются в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор