Я пытался решить вариант задачи о ранце, который выглядит следующим образом:
Это общая проблема ранца 0-1, но есть Q запросов (n, k) запрашивая максимальное значение, полученное с использованием первых n элементов и k емкости, где n варьируется от 1 до всех элементов, а k варьируется от 1 до некоторой максимальной емкости.
Однако выгода заключается в том, что вы не можете использовать O (n * k) память, только линейную O (k) память. Кроме того, каждый запрос кодируется, и его можно декодировать только путем решения предыдущего запроса.
Я застрял, потому что в любой момент я могу получить доступ только к одной строке таблицы DP, но мне нужно знать ответ к предыдущему запросу, и я не могу решить проблему ранца Q раз. Как бы я решил это?