Рюкзак с оптимизацией памяти

Полная таблица требует n умножить на cap ячеек памяти, что может стать проблемой на больших входных данных. Оптимизация памяти сводит её к одной повторно используемой строке.

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

Храните один массив dp длины cap+1. При обработке каждого предмета изменяйте его на месте, чтобы он представлял новую строку.

Если перебирать вместимость слева направо, dp[w - wt[i]] может быть уже обновлено для этого же предмета. Тогда Вы сможете взять предмет i дважды.

Решение — перебирать вместимость от большего значения к меньшему. Движение назад гарантирует, что dp[w - wt[i]] всё ещё хранит значение из предыдущей строки.

При вычислении dp[w] меньший индекс w - wt[i] в этом проходе ещё не был изменён, поэтому он содержит значение из предыдущей строки, как и требуется.

Вместимость меньше wt[i] не позволяет поместить предмет, поэтому цикл останавливается на wt[i]. Пропуск этих значений экономит несколько лишних итераций.

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

После обработки всех предметов dp[cap] хранит максимальную ценность. Это то же число, которое дала бы двумерная таблица, но памяти требуется значительно меньше.

Вы не ускорили алгоритм: он по-прежнему выполняет работу порядка n умножить на cap. Вы лишь сократили объём памяти с квадратичного до линейного.

Этот приём выручает, когда cap велико и двумерная таблица превысила бы лимит памяти. Это стандартный приём на соревнованиях, который стоит запомнить.

Проверьте главное правило для одномерного рюкзака.

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