Задача о рюкзаке, её вариации и динамическое программирование.
Цитата из книги С. Дасгупта, Х. Пападимитриу, У. Вазирани «Алгоритмы».
Забравшийся в магазин вор нашёл больше добычи, чем он может унести с собой. Его рюкзак выдерживает не больше $W$ килограммов.
Ему надо выбрать какие-то из $n$ товаров веса $w_1, \ldots, w_n$ и стоимости $v_1, \ldots, v_n$.
Как найти самый дорогой вариант?
Пусть, например, рюкзак выдерживает $W =10$ килограммов, а в магазине
имеются следующие изделия:
Товар Вес Стоимость
1 6 30
2 3 14
3 4 16
4 2 9
Есть две разновидности этой задачи. Если каждый товар имеется в
неограниченном количестве, то оптимально будет взять товар номер 1 и две
штуки товара номер 4 (общая стоимость: 48). Если же каждый товар есть в
единственном экземпляре (как в художественной галерее), тогда оптимальным будет набор из 1 и 3 (стоимость: 46).
Полиномиальных по времени алгоритмов для этих двух задач, скорее всего, не существует.
Однако динамическое программирование позволяет решить обе задачи (в случае целых весов) за время
$O(nW)$, которое вполне допустимо для малых $W$, но всё же не является полиномиальным, так как размер входа пропорционален $\log W$, а не $W$.
Задача о рюкзаке с повторениями
Начнём с варианта с повторениями.
Как обычно, важно правильно выбрать подзадачи.
В данном случае есть два естественных способа: рассмотреть рюкзак меньшей ёмкости $w\leqslant W$ (для краткости максимально допустимый вес
мы называем «ёмкостью») или же меньшее число товаров (скажем, товары $1, 2, \ldots, j$, где $j \leqslant n$).
Для того чтобы понять, какой подход действительно работает, обычно приходится немного поэкспериментировать.
Попробуем взять рюкзак меньшей ёмкости и положим
$K[w]$=максимально возможная стоимость для рюкзака ёмкости $w$.
Можем ли мы выразить $K[w]$ через ответы для меньших подзадач?
Ясно, что если в оптимальное заполнение рюкзака ёмкости $w$ входит товар $i$, то без одной штуки этого товара мы получим оптимальное заполнение рюкзака ёмкости $w − w_i$.
Другими словами, $K[w]$ — это просто $K[w − w_i] + v_i$ для некоторого $i$.
Мы не знаем, для какого именно $i$, поэтому нам нужно перебрать все возможные варианты:
$K[w] = \max_{i: w_i\leqslant w} \{K[w − w_i]+ v_i \}$,
где, как обычно, максимум по пустому множеству считается равным 0.
Получаем простой алгоритм:
$K[0] = 0$
для $w$ от 1 до $W$:
$K[w] = \max_{i: w_i\leqslant w} \{K[w − w_i]+ v_i \}$
вернуть $K[W]$
Алгоритм последовательно заполняет массив размера $W + 1$. Значение
каждой ячейки вычисляется за время $O(n)$, общее время работы $O(nW)$.
Задача о рюкзаке без повторений
Теперь рассмотрим вариант задачи, когда каждый товар есть в одном экземпляре.
Тогда воспользоваться подзадачами из прошлого решения не удаётся,
поскольку надо как-то учитывать, что мы уже взяли.
Сделаем это, добавив второй параметр $0\leqslant j \leqslant n$: обозначим через $K[w, j]$ максимальную стоимость
унесённого, если разрешается уносить лишь товары $1,\ldots, j$ и общий вес должен быть не больше $W$.
Исходная задача: найти $K[W, n]$.
Теперь нужно научиться выражать $K[w, j]$ через результаты для меньших
подзадач. Это несложно. В оптимальном заполнении товар $j$ либо участвует,
либо нет:
$K[w, j]=\max\{K[w − w_j , j −1]+ v_j , K[w, j −1]\}$
(первый член берётся, только если $w_j \leqslant w$.)
Другими словами, можно выразить $K[w, j]$ через результаты подзадач $K[·, j −1]$.
Алгоритм заполняет двумерный массив из $W + 1$ строки и $n + 1$ столбца.
Каждая ячейка заполняется за время $O(1)$.
Поэтому несмотря на гораздо больший размер таблицы по сравнению с предыдущим алгоритмом общее
время работы остаётся прежним: $O(nW)$.
Получаем простой алгоритм:
для всех $j$, $w$: $K[0, j]=0$; $K[w, 0]=0$;
для $j$ от 1 до $n$:
для $w$ от 1 до $W$:
если $w_j > w$: $K[w, j] = K[w, j −1]$
иначе: $K[w, j] = \max\{K[w, j −1], K[w − w_j , j −1]+ v_j \}$
вернуть $K[W, n]$
Упражнения
A: Разложение в сумму кубов
Дано натуральное число $N$. Необходимо представить его в виде суммы точных кубов, содержащей
наименьшее число слагаемых. Программа должна вывести это число слагаемых.
Программа получает на вход натуральное число $N$, не превосходящее $10^6$.
Программа должна вывести единственное натуральное число — ответ на вопрос задачи.
33
5
IDE
B: Рюкзак без повторов: точный вес
Дано $N$ золотых слитков массой $m_1, \ldots, m_N$. Ими наполняют рюкзак, который выдерживает
вес не более $M$. Можно ли набрать вес в точности $M$?
В первой строке вводится натуральное число $N$ ($N < 100$) и натуральное число $M$ ($M < 10^5$).
Во второй строке вводятся $N$ натуральных чисел $m_i$ ($m_i$ < 100).
Выведите YES или NO.
1 5968
18
NO
IDE
C: Рюкзак без повторов: наибольший вес
Дано $N$ золотых слитков массой $m_1, \ldots, m_N$. Ими наполняют рюкзак, который выдерживает
вес не более $M$. Какую наибольшую массу золота можно унести в таком рюкзаке?
В первой строке вводится натуральное число $N$ ($N < 100$) и натуральное число $M$ ($M < 10000$).
Во второй строке вводятся $N$ натуральных чисел $m_i$, не превышающих 100.
Выведите одно целое число — наибольшую возможную массу золота, которую можно унести
в данном рюкзаке.
2 3195
38 41
79
IDE
D: Банкомат
В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный
банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи
минимального числа банкнот, считая, что запас банкнот каждого номинала неограничен.
Помогите Национальному банку решить эту задачу.
Первая строка входных данных содержит натуральное число $N$ не превосходящее 100 —
количество номиналов банкнот в обращении. Вторая строка входных данных содержит $N$
различных натуральных чисел $x_1, \ldots, x_N$, не превосходящих $10^6$ — номиналы банкнот.
Третья строчка содержит натуральное число 𝑆, не превосходящее $10^6$ — сумму, которую
необходимо выдать.
Программа должна найти представление числа 𝑆 виде суммы слагаемых из множества $x_i$,
содержащее минимальное число слагаемых и вывести это представление на экран (в виде
последовательности чисел, разделенных пробелами). Если таких представлений существует
несколько, то программа должна вывести любое (одно) из них. Если такое представление
не существует, то программа должна вывести одно число -1.
5
1 3 7 12 32
40
32 7 1
IDE
E: 0-1 рюкзак — максимальная стоимость
Дано $N$ предметов массой $m_1, \ldots, m_N$ и стоимостью $c_1,\ldots,c_N$ соответственно.
Ими наполняют рюкзак, который выдерживает вес не более $M$. Какую наибольшую стоимость
могут иметь предметы в рюкзаке?
В первой строке вводится натуральное число $N$, не превышающее 100, и натуральное число
$M$, не превышающее 10000.
Во второй строке вводятся $N$ натуральных чисел $m_i$, не превышающих 100.
В третьей строке вводятся $N$ натуральных чисел $c_i$, не превышающих 100.
Выведите одно целое число: наибольшую возможную стоимость рюкзака.
4 6
2 4 1 2
7 2 5 1
13
Сформулируйте различные жадные стратегии для этой задачи и приведите контрпример
для каждой из них.
IDE
F: 0-1 рюкзак — максимальная стоимость с восстановлением ответа
Дано $N$ предметов массой $m_1, \ldots, m_N$ и стоимостью $c_1,\ldots,c_N$ соответственно.
Ими наполняют рюкзак, который выдерживает вес не более $M$. Определите набор предметов,
который можно унести в рюкзаке, имеющий наибольшую стоимость.
В первой строке вводится натуральное число $N$, не превышающее 100, и натуральное число
$M$, не превышающее 10000.
Во второй строке вводятся $N$ натуральных чисел $m_i$, не превышающих 100.
В третьей строке вводятся $N$ натуральных чисел $c_i$, не превышающих 100.
Выведите номера предметов (числа от 1 до $N$), которые войдут в рюкзак наибольшей
стоимости.
4 6
2 4 1 2
7 2 5 1
1
3
4
IDE
G: 0-1 рюкзак — точный вес, минимум предметов
Дано $N$ предметов массой $m_1, \ldots, m_N$.
Ими наполняют рюкзак, который выдерживает вес не более $M$. Как набрать вес в точности
$M$, используя как можно меньше предметов?
Первая строка входных данных содержит натуральное число $N$, не превышающее 100, и
натуральное число $M$, не превышающее 10000.
Во второй строке находится N натуральных чисел $m_i$, не превышающих 100.
Выведите наименьшее необходимое число предметов или 0, если набрать данный вес невозможно.
4 6
4 2 3 1
2
IDE
H: Гирьки — две кучки равной массы
Дан набор гирек массой $m_1, \ldots, m_N$. Можно ли их разложить на две чаши весов, чтобы
они оказались в равновесии?
Первая строка входных данных содержит натуральное число $N$, не превышающее 100.
Далее идет $N$ натуральных чисел $m_i$, не превышающих 100.
Программа должна вывести YES, если гирьки можно разложить на две кучки равной массы
или NO в противном случае
4
4 2 3 1
YES
IDE
I: Гирьки — две кучки равной массы с восстановлением ответа
Дан набор гирек массой $m_1, \ldots, m_N$. Разделите этот набор на две кучки равной массы,
содержащие равное число гирек.
Первая строка входных данных содержит натуральное число $N$, не превышающее 100.
Далее идет $N$ натуральных чисел $m_i$, не превышающих 100.
Необходимо вывести в первой строчке номера гирек (числа от 1 до $N$), входящие в первую
кучку, во второй строчке — номера гирек во второй кучке.
Если задача не имеет решения, выведите число 0.
4
4 2 3 1
2 3
1 4
IDE
J: Гирьки — три кучки равной массы с восстановлением ответа
Дан набор гирек массой $m_1, \ldots, m_N$. Можно ли их разложить на три кучки равной массы?
Первая строка входных данных содержит натуральное число $N$, не превышающее 60. Далее
идет $N$ натуральных чисел $m_i$, не превышающих 60.
Программа должна вывести номера гирек для каждого из наборов в три строки или строчку
No solution, если решения не существует.
5
4 2 3 1 5
5
1 4
2 3
IDE
K: Гирьки — четыре кучки равной массы с восстановлением ответа
Дан набор гирек массой $m_1, \ldots, m_N$. Можно ли их разложить на четыре кучки равной массы?
Первая строка входных данных содержит натуральное число $N$, не превышающее 14. Далее
идет $N$ натуральных чисел $m_i$, не превышающих 100.
Программа должна вывести номера гирек для каждого из наборов в три строки или строчку
No solution, если решения не существует.
8
10 20 30 40 50 60 70 80
1 8
2 7
3 6
4 5
IDE
L: Гирьки — три кучки равного размера и равной массы
Дан набор гирек массой $m_1, \ldots, m_N$. Разделите его на три кучки равной масссы, содержащие
равное число гирек.
Первая строка входных данных содержит натуральное число $N$, не превышающее 18. Далее
идет $N$ натуральных чисел $m_i$, не превышающих 100.
Программа должна вывести номера гирек для каждого из наборов в три строки или строчку
No solution, если решения не существует.