Задача о рюкзаке — Википедия с видео // WIKI 2

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

Формулировка задачи[править]

Дано [math]N[/math] предметов, [math]W[/math] — вместимость рюкзака, [math]w={w_{1},w_{2},dots,w_{N}}[/math] — соответствующий ему набор положительных целых весов, [math]p={p_{1},p_{2},dots,p_{N}}[/math] — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин [math]B={b_{1},b_{2},dots,b_{N}}[/math], где [math]b_{i} = 1 [/math], если предмет [math]n_i[/math] включен в набор, [math] b_{i} = 0 [/math], если предмет [math]n_i[/math] не включен, и такой что:

  1. [math]b_{1} w_{1}+ dots + b_{N} w_{N} leqslant W[/math]
  2. [math]b_{1} p_{1}+ dots + b_{N} p_{N} [/math] максимальна.

Формулировка задачи о рюкзаке

Приведём классическую формулировку задачи о рюкзаке (задачи о ранце).

Условие: Имеется рюкзак с ограниченной вместимостью по массе; также имеется набор вещей с определенным весом и ценностью. Необходимо подобрать такой набор вещей, чтобы он помещался в рюкзаке и имел максимальную ценность (стоимость).

Задача о рюкзаке (задача о ранце)

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

0-1 Рюкзак

В самой простой форме задача о рюкзаке формулируется так: > Даны (n) предметов с весами (a_1,ldots,a_n). Определите, на какой максимальный вес можно набрать предметов в рюкзак вместимости (W).

Для решения этой задачи воспользуемся динамическим программированием. Обозначим за (dp[i][j]) состояние, когда мы рассмотрели первые (i) предметов и набрали ими (j) веса. (dp[i][j]=True), если такая ситуация возможна, иначе (dp[i][j]=False).

Для каждого состояния (dp[i][j]), которое возможно получить, мы можем либо взять предмет номер (i) и попробовать обновить ответ из состояния (dp[i-1][j-a[i]]), либо не брать его и обновить ответ из (dp[i-1][j]). Очевидно, что мы можем получить 0 веса, рассмотрев 0 предметов.

dp[0][0] = Truefor i in range(1, n + 1): for j in range(0, W + 1): dp[i][j] = dp[i – 1][j] if a[i] <= j and dp[i – 1][j – a[i]]: dp[i][j] = True

Ответом будет максимальное (j), такое что (dp[n][j]=True). Таким образом, мы получили решение за (O(nW))

0-1 Рюкзак со стоимостями

Немного усложним задачу. Пусть, теперь предметы имеют не только веса, но и стоимости (c_1,ldots,c_n). Соответственно, надо набрать предметов с наибольшей суммарной стоимостью, но весом не превосходящим (W). Теперь в (dp[i][j]) будем хранить не просто возможно ли получить из первых (i) предметов набор веса (j), а максимальную суммарную стоимость такого набора. Если же такой набор получить невозможно, то по-прежнему (dp[i][j]=0). Переходы такие же как и в прошлой задаче. Изначально (dp) заполнено 0, так как для любого непустого набора мы пока не знаем, как его получить, а путой набор имеет стоимость 0.

for i in range(1, n + 1): for j in range(0, W + 1): dp[i][j] = dp[i – 1][j] if a[i] <= j: dp[i][j] = max(dp[i][j], dp[i – 1][j – a[i]] + c[i])

Ответом на задачу будет максимальное (dp[n][j]). Такое решение тоже работает за (O(nW)).

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

Рюкзак с ограниченным числом предметов

Пусть, теперь предметов каждого типа может быть несколько, то есть даны не только веса и стоимости, но и максимальные количества каждого из предметов (k_1,ldots,k_n). Тогда для каждого состояния (dp[i][j]) переберем, сколько мы взяли предметов такого типа и сделаем переход из каждого соответствующего состояния. Понятно, что мы не сможем взять более, чем (lfloorfrac{W}{a_i}rfloor) предметов каждого типа.

for i in range(1, n + 1): for j in range(0, W + 1): for cnt in range(min(k[i], W // a[i]) + 1): if a[i] * cnt <= j: dp[i][j] = max(dp[i][j], dp[i – 1][j – a[i] * cnt] + c[i] * cnt)

Такое решение работает за (O(nW^2)), так как (k_i) могут быть очень большими, а (a_1=1).

Можете попробовать решить эту задачу за (O(nWlog K)), где (K) — максимальное из (k_i).

Рюкзак с неограниченным числом предметов

Пусть, теперь каждого предмета будет не (k_i), а вообще бесконечно. Оказывается, задача стала только проще. Вернемся к обычному рюкзаку с весами и стоимостями. Единственное отличие будет в том, что теперь мы можем делать второй переход не из предыдущей строки, а прямо из текущей. При этом заметим, что для каждого состояния достаточно рассмотреть взятие только одного предмета данного типа, поскольку взятие двух и более будет рассмотрено одновременно.

for i in range(1, n + 1): for j in range(0, W + 1): dp[i][j] = dp[i – 1][j] if a[i] <= j: dp[i][j] = max(dp[i][j], dp[i][j – a[i]] + c[i])

Такое решение работает за (O(nW)).

Если (W) велико, а (a_i) достаточно малы, можно построить решение за (O(n + A^3)), где (A) — максимальное из (a_i). Заметим, что если (W) достаточно большое, то большая часть рюкзака будет занята предметами одного и того же типа с максимальной удельной стоимостью. Можно доказать, что одним и тем же предметом будет занято не менее (W-A^2) веса. Таким образом, можно за (O(n)) выбрать предмет с максимальным удельным весом, а для оставшихся предметов запустить предыдущий алгоритм, который сработает за (O(A^3)), так как имеет смысл рассматривать не более (A) предметов, а максимальный вес (A^2).

Восстановление ответа

Во всех рассмотренных задачах восстановление ответа делается стандартным образом: нужно из ответа пройтись обратно до начала.

  • первый способ – это построить массив prev, где для каждой ячейки (dp[i][j]) хранить, берем мы предмет i, или не берем предмет (i).
  • второй способ – это определять это на ходу, смотря, какое из значений (dp[i – 1][j]) или (dp[i – 1][j – a[i]] + c[i]) больше.

Классическая постановка задачи

Пусть имеется набор предметов, каждый из которых имеет два параметра — масса и ценность. Также имеется рюкзак определённой грузоподъёмности. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом ограничение рюкзака на суммарную массу.

Математически задача формулируется следующим образом: имеется n{displaystyle n}n грузов. Для каждого i{displaystyle i}i-го груза определены его масса wi>0{displaystyle w_{i}>0}w_{i}>0 и ценность vi>0{displaystyle v_{i}>0}v_{i}>0, i=1,2,…,n{displaystyle i=1,2,…,n}i=1,2,...,n. Ограничение суммарного веса предметов в рюкзаке задаётся грузоподъёмностью W{displaystyle W}W. Необходимо

максимизировать ∑i=1nvixi{displaystyle sum _{i=1}^{n}v_{i}x_{i}}{displaystyle sum _{i=1}^{n}v_{i}x_{i}}с ограничениями ∑i=1nwixi≤W{displaystyle sum _{i=1}^{n}w_{i}x_{i}leq W}{displaystyle sum _{i=1}^{n}w_{i}x_{i}leq W} и xi∈{0,1}{displaystyle x_{i}in {0,1}}{displaystyle x_{i}in {0,1}} [1].

Варианты задачи о рюкзаке

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

  1. Рюкзак 0-1 (англ. 0-1 Knapsack Problem)[2]: не более одного экземпляра каждого предмета.
  2. Ограниченный рюкзак (англ. Bounded Knapsack Problem)[3]: не более заданного числа экземпляров каждого предмета.
  3. Неограниченный рюкзак (англ. Unbounded Knapsack Problem)[3]: произвольное количество экземпляров каждого предмета.
  4. Рюкзак с мультивыбором (англ. Multiple-choice Knapsack Problem)[4]: предметы разделены на группы, и из каждой группы требуется выбрать только один предмет.
  5. Множественный рюкзак (англ. Multiple Knapsack Problem)[5]: есть несколько рюкзаков, каждый со своим максимальным весом. Каждый предмет можно положить в любой рюкзак или оставить.
  6. Многомерный рюкзак (англ. Multi-dimensional knapsack problem): вместо веса дано несколько разных ресурсов (например, вес, объём и время укладки). Каждый предмет тратит заданное количество каждого ресурса. Надо выбрать подмножество предметов так, чтобы общие затраты каждого ресурса не превышали максимума по этому ресурсу, и при этом общая ценность предметов была максимальна[4].
  7. Квадратичная задача о рюкзаке (англ. Quadratic knapsack problem): суммарная ценность задается неотрицательно определённой квадратичной формой[6].

Метод динамического программирования[править]

Пусть [math]A(k, s)[/math] есть максимальная стоимость предметов, которые можно уложить в рюкзак вместимости [math]s[/math], если можно использовать только первые [math]k[/math] предметов, то есть [math]{n_1,n_2,dots,n_k}[/math], назовем этот набор допустимых предметов для [math]A(k,s)[/math].

[math]A(k, 0) = 0[/math]

[math]A(0, s) = 0[/math]

Найдем [math]A(k, s)[/math]. Возможны 2 варианта:

  1. Если предмет [math]k[/math] не попал в рюкзак. Тогда [math]A(k, s)[/math] равно максимальной стоимости рюкзака с такой же вместимостью и набором допустимых предметов [math]{n_1,n_2,dots,n_{k-1}}[/math], то есть [math]A(k,s) = A(k-1, s)[/math]
  2. Если [math]k[/math] попал в рюкзак. Тогда [math]A(k, s)[/math] равно максимальной стоимости рюкзака, где вес [math]s[/math] уменьшаем на вес [math]k[/math]-ого предмета и набор допустимых предметов [math]{n_1,n_2,dots,n_{k-1}}[/math] плюс стоимость [math]k[/math], то есть [math]A(k-1, s-w_k) + p_k[/math]

[math]A(k, s) =begin{cases} A(k-1, s), & b_k = 0 \ A(k-1, s-w_k) + p_k, & b_k = 1 \end{cases}[/math]

То есть: [math]A(k,s) = max(A(k-1,s), A(k-1,s-w_{k}) + p_{k})[/math]

Стоимость искомого набора равна [math]A(N,W)[/math], так как нужно найти максимальную стоимость рюкзака, где все предметы допустимы и вместимость рюкзака [math]W[/math].

Восстановим набор предметов, входящих в рюкзак

Будем определять, входит ли [math]n_i[/math] предмет в искомый набор. Начинаем с элемента [math]A(i,w)[/math], где [math]i = N[/math], [math]w = W[/math]. Для этого сравниваем [math]A(i,w)[/math] со следующими значениями:

  1. Максимальная стоимость рюкзака с такой же вместимостью и набором допустимых предметов [math]{n_1,n_2,dots,n_{i-1}}[/math], то есть [math]A(i-1, w)[/math]
  2. Максимальная стоимость рюкзака с вместимостью на [math]w_i[/math] меньше и набором допустимых предметов [math]{n_1,n_2,dots,n_{i-1}}[/math] плюс стоимость [math]p_i[/math], то есть [math]A(i-1, w-w_i)+p_i[/math]

Заметим, что при построении [math]A[/math] мы выбирали максимум из этих значений и записывали в [math]A(i, w)[/math]. Тогда будем сравнивать [math]A(i, w)[/math] c [math]A(i-1, w)[/math], если равны, тогда [math]n_i[/math] не входит в искомый набор, иначе входит.

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

Максимазация ценности

Как максимизировать суммарную ценность объектов так, чтобы суммарная площадь не превышала 2000 дм2? Можно попробовать перебрать все возможные комбинации и рассчитать суммарную ценность для каждой из комбинаций. Решение получится, если выбрать максимальную суммарную ценность для 2000 дм2. Но вот незадача: и комбинаторика, и теория множеств утверждают, что 29 предметов дают 2²⁹ возможных комбинаций выбора предметов.

То есть более 536 миллионов. Похоже, такой перебор займёт некоторое время. Нельзя ли быстрее?

Стоит подумать о других вариантах. Что если начать с наиболее ценного предмета, затем следующего за ним по ценности, и так до тех пор, пока не заполнятся 20 квадратных метров? Такой алгоритм явно быстрее. Но даст ли он оптимальное решение? Есть сомнения. Как быстро решить задачу и найти лучшее решение?

Примечание: описанные выше случаи соответствуют полному перебору (метод «грубой силы», англ. brute force) и жадному (англ. greedy) алгоритму.

***

Соответствующий класс проблем называют задача о рюкзаке. Своё название проблема получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.

К счастью, знакомый слышал об этом классе задач и подсказал вам более разумный способ справиться с проблемой. Он объяснил, что можно рекурсивно разделить проблему на более мелкие подзадачи. Сохраняя результаты в ячейках таблицы мемоизации и используя их на следующих итерациях, вы быстро найдёте оптимальное решение. Вы как бы обменяете программную память на время. То есть воспользуетесь методом динамического программирования.

Ограниченный рюкзак[править]

Задача:
Ограниченный рюкзак (англ. Bounded Knapsack Problem) — обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.

Формулировка Задачи[править]

Каждый предмет может быть выбран ограниченное [math]b_i[/math] число раз.Задача выбрать число [math]x_i[/math] предметов каждого типа так, чтобы

  • максимизировать общую стоимость: [math]sum_{i=1}^N p_ix_i[/math];
  • выполнялось условие совместности: [math]sum_{i=1}^N w_ix_i leqslant W[/math];

где [math] x_i in (0,1,dots,b_i)[/math] для всех [math] i= 1,2,dots,N[/math].

Варианты решения[править]

При небольших [math]b_i[/math] решается сведением к классической задаче о рюкзаке. В иных случаях:

  • Методом ветвей и границ.
  • Методом динамического программирования.

Метод динамического программирования[править]

Пусть [math]d(i,c)[/math] максимальная стоимость любого возможного числа предметов типов от 1 до [math]i[/math], суммарным весом до [math]c[/math].

Заполним [math]d(0,c)[/math] нулями.

Тогда меняя i от 1 до [math]N[/math], рассчитаем на каждом шаге [math]d(i,c)[/math], для [math]c[/math] от 1 до [math]W[/math], по рекуррентной формуле:

[math]d(i,c) = max(d(i, c), d(i – 1, c – lw_i) + lp_i) [/math] по всем целым [math] l [/math] из промежутка [math] 0 leqslant l leqslant min(b_i,lfloor c/w_i rfloor)[/math].

Если не нужно восстанавливать ответ, то можно использовать одномерный массив [math]d(c)[/math] вместо двумерного.

После выполнения в [math] d(N,W) [/math] будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Реализация[править]

for i = 0 to w //База d[0][i] = 0for i = 1 to n for c = 1 to w //Перебираем для каждого i, все вместимости d[i][c] = d[i – 1][c] for l = min(b[i], c / w[i]) downto 1 //Ищем l для которого выполняется максимум d[i][c] = max(d[i][c], d[i – 1][c – l * w[i]] + p[i] * l)

Сложность алгоритма [math]O(NW^2)[/math].

Приложения

Доподлинно неизвестно, кто первым привел математическую формулировку задачи о рюкзаке. Одно из первых упоминаний о ней можно найти в статье Джорджа Балларда Мэтьюса  (англ.) (рус.[20][21], датированной 1897 годом. Интенсивное изучение данной проблемы началось после публикации Д. Б Данцигом в 1957 году книги «англ. Discrete Variable Extremum Problem»[22], особенно в 70—90-е годы XX века, как теоретиками, так и практиками[2]. Во многом интерес был вызван достаточно простой формулировкой задачи, большим числом её разновидностей и свойств и в то же время сложностью их решения. В 1972 году данная задача вошла в список М. Карпа NP-полных задач (статья англ. «Reducibility Among Combinatorial Problems»)[23].

Наглядная интерпретация задачи о рюкзаке привела к тому, что она нашла применение в разных областях знаний: в математике, информатике и на стыке этих наук — в криптографии. В одной из работ по вычислительной лингвистике[24] предложена формулировка задачи автоматического реферирования текстов  (англ.) (рус., частный случай которой соответствует постановке задачи о рюкзаке.

На основе задачи о рюкзаке был создан первый алгоритм асимметричного шифрования. Впервые идея криптографии с открытыми ключами была представлена Уитфилдом Диффи и Мартином Хеллманом на Национальной компьютерной конференции (англ. National Computer Conference) 1976 года[25][26].

Также задача о рюкзаке может служить моделью для большого числа промышленных задач[2][27]:

  • Размещение грузов на складе минимальной площади.
  • Раскройка ткани — из имеющегося куска материала получить максимальное число выкроек определённой формы.
  • Расчет оптимальных капиталовложений.

Демонстрация работы программы

Итак, решим задачу о рюкзаке с помощью написанной программы. Исходные данные о предметах – из таблицы выше; вместимость ранца – 8 килограмм.

Задача о рюкзаке - Исходные данные

Нажмём кнопку “Решить” и получим решение задачи. Оно приведено в таблице на окне программы:

Задача о рюкзаке - Решение задачи

Скачать исходник программы, либо перейти в репозиторий проекта на GitHub:

Скачать исходникРепозиторий проекта на GitHub

Надеемся, что данная статья и программа помогли Вам разобраться с решением задачи о рюкзаке на языке C#. Спасибо за прочтение!

Задача о рюкзаке: алгоритм, решение

4.59 (91.82%) 22 votes

Задание

Решите как можно больше задач из этих двух контестов:

https://informatics.msk.ru/mod/statements/view.php?id=35888

https://informatics.msk.ru/mod/statements/view.php?id=33257 ### Дополнительная сложная задача https://csacademy.com/contest/round-61/task/strictly-increasing-array/statement/

Источники информации[править]

  • Дистанционная подготовка по информатике
  • Код для нескольких задач семейства на всевозможных языках
  • David Pisinger Knapsack problems. — 1995
  • Silvano Martello, Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations — 1990 г. — ISBN 0-471-92420-2
    1. http://hjemmesider.diku.dk/~pisinger/codes.html
    2. Pisinger D (1999). “Linear Time Algorithms for Knapsack Problems with Bounded Weights”. Journal of Algorithms, Volume 33, Number 1, October 1999, pp. 1–14
    3. Koiliaris, Konstantinos; Xu, Chao (2015-07-08). “A Faster Pseudopolynomial Time Algorithm for Subset Sum”.
    4. Bringmann K. A near-linear pseudopolynomial time algorithm for subset sum[C]//Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2017: 1073-1084
Рейтинг
( 1 оценка, среднее 5 из 5 )
Загрузка ...