Достопочтенный SergeyACTIVITI в своём посте поведал нам про такую полезную вещь, как задача о рюкзаке, решение которой с успехом реализовано в решателях COIN-OR или GLPK. А что же внутри?
Итак, пусть у нас есть рюкзак объёма W, и список из n вещей, у каждой из которых есть объём v[i] и стоимость c[i], и каждую из которых можно брать сколько угодно раз. При этом все объёмы и все стоимости будут положительными и целыми. Как же работает алгоритм?
Заведём массив max длины W+1, в котором мы по итогам работы алгоритма получим наибольшую стоимость, которую может иметь набор вещей, занимающий данный объём — для каждого объёма от 0 до W включительно.
А точнее, после k итераций мы получим для каждого объёма i max[i] — максимальную возможную стоимость набора вещей объёма i, в котором могут быть только первые k вещей.
Сразу понятно, что изначально надо инициализировать max[0] = 0. Что же остальные элементы max? Не используя никаких вещей, можно получить только набор веса 0. Значит, в max[i] (0 < i <= W) нужно записать что-то, что будет хуже, чем любая возможная стоимость набора веса i. Например, -1.
После этого надо сделать n итераций.
На k-той итерации мы делаем следующее.
До итерации в массиве в каждом элементе max[i] записана максимальная возможная стоимость набора вещей веса i, который составлен из вещей 0..k-1. Каждый раз, рассматривая элемент max[i], мы добьёмся того, чтобы там была записана максимальная возможная стоимость набора вещей веса i, который составлен из вещей 0..k. Для этого проверим, в оптимальном наборе вообще есть k-тая вещь, хотя бы одна? Если нет, то в max[i] уже записана оптимальная стоимость. Если есть, то, если из этого набора выкинуть одну k-тую вещь, то получится оптимальный набор вещей объёма i-v[k], оставленный из вещей 0..k. Но последний уже записан в max[i-v[k]]! Значит, надо просто сравнить величины max[i] и max[i-v[k]] + c[k] (если, конечно, i >= v[k]). Максимальную из них и надо записать в max[i].
Итак, после k-той итерации мы полчим в каждом max[i] наибольшую стоимость, которую может имет набор вещей, составленный из вещей. Значит, после n итераций мы получим именно то, что и обещалось. Осталось дело техники: пройтись по массиву max[i] и выбрать в нём максимальный элемент.
Как несложно заметить, ассимптотика времени работы алгоритма будет O(W*n), и используемой памяти — O(W).
Вариации:
1. Когда надо получить не только стоимость, но и сам набор.
Кроме массива max, запишем ещё и массив prev. В него мы будем записывать, какую вещь мы последний раз положили в набор. То есть, если при сравнении max[i] и max[i-v[k]] + c[k] оказалось, что max[i-v[k]] + c[k] лучше — это означает, что в оптимальном наборе веса i должен быть k-тый предмет. Таким образом, если мы выяснили, что оптимальная стоимость max[i] достигается при наборе веса i, то можно записать, что мы добавили в набор вещь prev[i]. И перейти к оптимальному набору веса i — v[prev[i]]. Там тоже посмотреть, какую вещь взяли в последний раз. И так далее, пока не дойдём до нуля.
2. Когда каждую вещь можно брать только один раз.
Тут всё ещё проще: надо просто в каждй итерации идти по массиву не снизу вверх, а сверху вниз, то есть, от W к 0. Тогда получится, что при рассмотрении max[i-v[k]], там всё ещё будет записано, набор какой максималльной стоимости веса i — v[k] можно получить, используя только вещи 0..k-1. Следовательно, если получится, что в оптимальном наборе надо использовать k-тую вещь, то она будет использована только один раз.
3. Выбор значения, как можно более близкого к данному.
Если нет стоимостей, то данный алгоритм, очевидно, помогает как можно сильнее набить рюкзак. Или же, если речь идёт не о рюкзаке, и неважно, что общий объём вещей не больше объёма рюкзака, можно из нескольких чисел с помощью сложения получить число, как можно более близкое к данному.
В всех случаях ассимптотика времени работы и используемой памяти та же.
4. Когда каждую вещь можно брать определённое количество раз.
За эту вариацию спасибо lipstick.
Есть вариация задачи, в которой вещь с номером i можно брать от 0 до q[i] раз. Конечно, можно «размножить» i-ю вещь на q[i] единиц и решить задачу о 0-1 рюкзаке. Однако, сложность такого решения будет O(W * ∑q[i]), что не очень хорошо. На самом деле, можно поступить хитрее.
Пусть q[i] = 1 + 2 + 4 + 8 +… + 2^k + r[i], где r[i] < 2^(k+1).
Тогда рассмотрим k+2 предмета объёмом 1*v[i], 2*v[i], ..., 2^k*v[i], r[i]*v[i] и стоимостью 1*c[i], 2*c[i], ..., 2^k*c[i], r[i]*c[i] соответственно.
(«Названия» новых предметов — «1 i-я вещь», «2 i-ых вещи», «4 i-ых вещи» и т. д.)
Ясно, что выбирая различные подмножества этих k+2 предметов, можно получить любое количество (от 0 до q[i]) вещей типа i. Т. е. вместо «размножения» вещей i-го типа на q[i] единиц, мы сумели ограничиться k+2 = O(log q[i]) единицами.
Такой метод будет иметь сложность порядка O(W * ∑log q[i]), что куда более эффективно, чем «наивное» решение.
P.S. Кому не лень, можете подредактировать статью в википедии — там написано что-то не то =)
Итак, пусть у нас есть рюкзак объёма W, и список из n вещей, у каждой из которых есть объём v[i] и стоимость c[i], и каждую из которых можно брать сколько угодно раз. При этом все объёмы и все стоимости будут положительными и целыми. Как же работает алгоритм?
Заведём массив max длины W+1, в котором мы по итогам работы алгоритма получим наибольшую стоимость, которую может иметь набор вещей, занимающий данный объём — для каждого объёма от 0 до W включительно.
А точнее, после k итераций мы получим для каждого объёма i max[i] — максимальную возможную стоимость набора вещей объёма i, в котором могут быть только первые k вещей.
Сразу понятно, что изначально надо инициализировать max[0] = 0. Что же остальные элементы max? Не используя никаких вещей, можно получить только набор веса 0. Значит, в max[i] (0 < i <= W) нужно записать что-то, что будет хуже, чем любая возможная стоимость набора веса i. Например, -1.
После этого надо сделать n итераций.
На k-той итерации мы делаем следующее.
До итерации в массиве в каждом элементе max[i] записана максимальная возможная стоимость набора вещей веса i, который составлен из вещей 0..k-1. Каждый раз, рассматривая элемент max[i], мы добьёмся того, чтобы там была записана максимальная возможная стоимость набора вещей веса i, который составлен из вещей 0..k. Для этого проверим, в оптимальном наборе вообще есть k-тая вещь, хотя бы одна? Если нет, то в max[i] уже записана оптимальная стоимость. Если есть, то, если из этого набора выкинуть одну k-тую вещь, то получится оптимальный набор вещей объёма i-v[k], оставленный из вещей 0..k. Но последний уже записан в max[i-v[k]]! Значит, надо просто сравнить величины max[i] и max[i-v[k]] + c[k] (если, конечно, i >= v[k]). Максимальную из них и надо записать в max[i].
Итак, после k-той итерации мы полчим в каждом max[i] наибольшую стоимость, которую может имет набор вещей, составленный из вещей. Значит, после n итераций мы получим именно то, что и обещалось. Осталось дело техники: пройтись по массиву max[i] и выбрать в нём максимальный элемент.
Как несложно заметить, ассимптотика времени работы алгоритма будет O(W*n), и используемой памяти — O(W).
Вариации:
1. Когда надо получить не только стоимость, но и сам набор.
Кроме массива max, запишем ещё и массив prev. В него мы будем записывать, какую вещь мы последний раз положили в набор. То есть, если при сравнении max[i] и max[i-v[k]] + c[k] оказалось, что max[i-v[k]] + c[k] лучше — это означает, что в оптимальном наборе веса i должен быть k-тый предмет. Таким образом, если мы выяснили, что оптимальная стоимость max[i] достигается при наборе веса i, то можно записать, что мы добавили в набор вещь prev[i]. И перейти к оптимальному набору веса i — v[prev[i]]. Там тоже посмотреть, какую вещь взяли в последний раз. И так далее, пока не дойдём до нуля.
2. Когда каждую вещь можно брать только один раз.
Тут всё ещё проще: надо просто в каждй итерации идти по массиву не снизу вверх, а сверху вниз, то есть, от W к 0. Тогда получится, что при рассмотрении max[i-v[k]], там всё ещё будет записано, набор какой максималльной стоимости веса i — v[k] можно получить, используя только вещи 0..k-1. Следовательно, если получится, что в оптимальном наборе надо использовать k-тую вещь, то она будет использована только один раз.
3. Выбор значения, как можно более близкого к данному.
Если нет стоимостей, то данный алгоритм, очевидно, помогает как можно сильнее набить рюкзак. Или же, если речь идёт не о рюкзаке, и неважно, что общий объём вещей не больше объёма рюкзака, можно из нескольких чисел с помощью сложения получить число, как можно более близкое к данному.
В всех случаях ассимптотика времени работы и используемой памяти та же.
4. Когда каждую вещь можно брать определённое количество раз.
За эту вариацию спасибо lipstick.
Есть вариация задачи, в которой вещь с номером i можно брать от 0 до q[i] раз. Конечно, можно «размножить» i-ю вещь на q[i] единиц и решить задачу о 0-1 рюкзаке. Однако, сложность такого решения будет O(W * ∑q[i]), что не очень хорошо. На самом деле, можно поступить хитрее.
Пусть q[i] = 1 + 2 + 4 + 8 +… + 2^k + r[i], где r[i] < 2^(k+1).
Тогда рассмотрим k+2 предмета объёмом 1*v[i], 2*v[i], ..., 2^k*v[i], r[i]*v[i] и стоимостью 1*c[i], 2*c[i], ..., 2^k*c[i], r[i]*c[i] соответственно.
(«Названия» новых предметов — «1 i-я вещь», «2 i-ых вещи», «4 i-ых вещи» и т. д.)
Ясно, что выбирая различные подмножества этих k+2 предметов, можно получить любое количество (от 0 до q[i]) вещей типа i. Т. е. вместо «размножения» вещей i-го типа на q[i] единиц, мы сумели ограничиться k+2 = O(log q[i]) единицами.
Такой метод будет иметь сложность порядка O(W * ∑log q[i]), что куда более эффективно, чем «наивное» решение.
P.S. Кому не лень, можете подредактировать статью в википедии — там написано что-то не то =)
