Как решать задачи на ДП такого типа (выбрать предметы, но без повторений)?

Question

[dalbio]

Есть задача: https://cses.fi/problemset/task/1158
Я понимаю как сделать когда можно повторять предметы,но когда нельзя не понимаю как.
Буду благодарен за ответ.

Comments

[Матвей Истомин]

Похоже на задачу о рюкзаке

[ayazer]

да, это именно задача о рюкзаке. И за последние пару дней она тут всплывала уже несколько раз.

dalbio ну так покажите что выходит и в каком месте не понятно. Может вы просто не с той стороны вообще начали решать

[dalbio]

Я плохо понимаю когда надо использовать матрицы в ДП.(Есть какие-нибудь признаки в задаче ,что нужна матрица как например в этой)?

Answer 1

[Wataru]

Это классическая задача о рюкзаке.

Можно составить такое ДП: F(c, k) - максимальное количество страниц, которые можно набрать из первых k книг общей стоимостью ровно c.

База: F(0,0) = 0, F(0,*) = F(*,0) = -infinity.
Пересчет:

F(c, k) = max(F(c-cost[k], k-1) + pages[k], F(c,k-1))

Это ДП приведено в википедии, например. Ответ - максимум по всем c F(c,k).

Есть одна хитрость при реализации - можно обойтись только одной строкой этой матрицы, если вам не нужно восстанавливать весь набор книг в ответе, а только его лучшее значение (только надо поменять параметры местами - строка размером с максимальную цену). Это сократит потребление памяти в K раз, если у вас K книг. На скорость работы решения это не влияет.

Сначала реализуйте все дп на матрице снизу вверх, двумя циклами.
Теперь, если вы будете гнать внутренний цикл с конца к началу, то вам не понадобится смотреть на уже переписанные на текущей итерации внешнего цикла значения, и можно забить на второй параметр ДП и просто переписывать строку на месте.

Answer 2

[profesor08]

Отсортируй книги по возрастанию цены за страницу. Потом выбери первые N книг, на сколько хватит денег.

Comments

[ayazer]

это один с вариантов жадного алгоритма, он не гарантируют нахождение лучшего ответа