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

Турист с ограничением по весу, вор с мешком, компания с бюджетом и списком проектов — все они решают один и тот же вопрос. Что взять, чтобы получить наибольшую ценность, не превысив предел? Это задача о рюкзаке, и динамическое программирование решает ее точно, когда веса — целые числа умеренной величины.

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

Задача

Есть n предметов, у каждого вес и стоимость, и рюкзак, вмещающий вес не более W. Нужно выбрать набор предметов, общий вес которого не превышает W, а общая стоимость как можно больше. Каждый предмет кладется целиком или остается снаружи, поэтому задача называется задачей о рюкзаке 0/1. Для n предметов существует 2ⁿ возможных наборов, так что перебрать их все вскоре становится невозможно.

Таблица

Пусть best[i][w] — наибольшая стоимость, которая помещается в вес w, если использовать только первые i предметов. Тогда best[0][w] = 0, а для каждой следующей строки есть два варианта: не брать предмет i, что дает best[i − 1][w], или, если его вес wᵢ помещается, положить его, что дает его стоимость плюс best[i − 1][w − wᵢ]. Большее из двух и есть best[i][w]. Если заполнять таблицу строка за строкой, обе нужные клетки всегда уже готовы.

Пример

Возьмем вместимость 7 и четыре предмета с весами 1, 3, 4 и 5 и стоимостями 1, 4, 5 и 7. Только с первым предметом любая вместимость от 1 и выше стоит 1. Если добавить второй, при вместимости 4 можно взять оба за 5. Если добавить третий, при вместимости 7 можно взять предметы 2 и 3 за 9. Четвертый предмет, весом 5 и стоимостью 7, вместе с предметом 1 дал бы 8 при вместимости 6 или 7, но 9 лучше, поэтому в правой нижней клетке 9: положите предметы весом 3 и 4.

Насколько это трудно?

Таблице нужно около n·W шагов. Это выглядит быстро, но W — это число, а число из d цифр может достигать 10 в степени d, поэтому работа растет экспоненциально с длиной входных данных. Задача о рюкзаке NP-трудна; она была одной из 21 NP-полной задачи Ричарда Карпа 1972 года. На практике таблица, метод ветвей и границ и хорошие приближенные схемы хорошо справляются с большими реальными задачами.

История и применение

Название восходит к математику Тобиасу Данцигу в начале XX века, а его сын Джордж Данциг в 1957 году предложил для нее классический жадный метод. Задачи о рюкзаке встречаются при составлении бюджета и выборе инвестиционного портфеля, при раскрое сырья с минимальными отходами, при погрузке грузов и даже в ранней криптографии с открытым ключом: криптосистема Меркла — Хеллмана 1978 года была построена на задаче о рюкзаке и через несколько лет была взломана.

Джордж Данциг (слева) получает Национальную научную медаль из рук президента Джеральда Форда в 1976 году. В 1957 году Данциг дал классический жадный метод для задачи о рюкзаке. Само название восходит к его отцу, Тобиасу Данцигу.
Джордж Данциг (слева) получает Национальную научную медаль из рук президента Джеральда Форда в 1976 году. В 1957 году Данциг дал классический жадный метод для задачи о рюкзаке. Само название восходит к его отцу, Тобиасу Данцигу.

Попробуйте сами

Откройте приложение, перейдите в вид «Таблица» и нажмите Шаг. Оранжевая клетка заполняется, а синие — это две клетки, которые она сравнивает: клетка прямо над ней и клетка в строке выше, левее на вес предмета. После последней клетки обратный ход поднимается оранжевым от правого нижнего угла, а уложенные предметы появляются под таблицей.

Часто задаваемые вопросы

Чем отличаются задачи о рюкзаке 0/1, ограниченная и неограниченная?

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

Бывает ли жадный метод правильным для задачи о рюкзаке?

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

Сколько памяти нужно таблице?

(n + 1)·(W + 1) клеток для полной таблицы — именно она нужна, чтобы восстановить предметы. Если нужна только наибольшая стоимость, достаточно одной строки из W + 1 клетки, которую заполняют справа налево.

Задача о рюкзаке — это то же самое, что задача о сумме подмножества?

Задача о сумме подмножества — частный случай, в котором стоимость каждого предмета равна его весу, а вопрос в том, можно ли заполнить рюкзак ровно. Она тоже NP-полна и решается такой же таблицей.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Попробовать задачу о рюкзаке