Задача о рюкзаке
Дано $n$ предметов с целыми неотрицательными весами $a_n$ и стоимостями $c_n$. Необходимо уложить часть предметов в рюкзак вместимостью $w$ так, чтобы сумма стоимостей была максимальна.
Решение
Вообще говоря, при произвольных весах предметов задача является $NP$-полной, то есть не решается за полиномиальное время. Однако в нашей версии задачи веса целые и неотрицательные, так что решение есть.
Воспользуемся методом динамического программирования:
Будем хранить в $dp[i][j]$ максимальную стоимость, которую можно получить, выбрав предметы из первых $i$ с суммарным весом не более $j$. Если набрать такой вес нельзя, будем хранить $0$.
База динамики - $dp[0][0] = 0$ (можно не взять ни одного предмета, получив вес $0$ и стоимость $0$).
Для пересчёта посмотрим, что происходит, когда мы добавляем $i$-тый предмет:
- Всегда можно отказаться брать новый предмет, тогда $dp[i][j] = dp[i - 1][j]$.
- Если $a[i] \leq j$, то мы можем взять предмет, и тогда $dp[i][j] = dp[i - 1][j - a[i]] + c[i]$.
В итоге получим формулу пересчёта:
\[dp[i][j] = \max\begin{cases} dp[i - 1][j] \\ dp[i - 1][j - a[i]] + c[i], \text{ если } j - a[i] \geq 0 \end{cases}\]Асимптотика
Ясно, что $i$ необходимо перебирать до $n$, в то время как вес можно перебирать до $w$. Итоговая сложность - $O(nw)$.