Как восстановить сам ответ в задаче о рюкзаке (а не только максимальную стоимость)?
Стандартный 0/1 рюкзак считает максимальную стоимость dp[W]. Но мне нужно вывести, какие именно предметы взяты. Как восстановить набор? Боюсь, что при сжатии до одномерного dp[w] информация о выборе теряется.
2 ответа
Есть два надёжных способа.
Способ 1 — двумерная таблица + обратный проход. Храним dp[i][w] (первые i предметов, вместимость w). После заполнения идём от dp[n][W] назад: если dp[i][w] != dp[i-1][w], значит предмет i взят.
int n, W;
vector<int> wt, cost;
vector<vector<long long>> dp(n + 1, vector<long long>(W + 1, 0));
for (int i = 1; i <= n; ++i)
for (int w = 0; w <= W; ++w) {
dp[i][w] = dp[i - 1][w]; // не берём
if (w >= wt[i - 1])
dp[i][w] = max(dp[i][w],
dp[i - 1][w - wt[i - 1]] + cost[i - 1]); // берём
}
// восстановление
vector<int> taken;
int w = W;
for (int i = n; i >= 1; --i)
if (dp[i][w] != dp[i - 1][w]) { // значение изменилось -> предмет i-1 взят
taken.push_back(i - 1);
w -= wt[i - 1];
}
Время и память . Память — главный риск (MLE), если велико.
Способ 2 — массив from/choice. Если ужимаешь до 1D ради скорости, заведи отдельный choice[i][w] (или храни предка перехода). Но для рюкзака способ 1 нагляднее и менее ошибкоопасен.
Если память не влезает, а восстановление нужно, есть приём Хиршберга (divide & conquer): считаешь рюкзак за времени и памяти, но восстановление набора делаешь рекурсивно, разбивая множество предметов пополам и совмещая префиксный и суффиксный 1D-DP. Получается время, память, глубина рекурсии. На олимпиадах это уже продвинутый трюк — обычно достаточно способа 1, если лимиты позволяют.
Типичная грабля при восстановлении в 1D: если идти по w в неправильном направлении при обновлении, предмет «возьмётся» несколько раз (получится неограниченный рюкзак) — для 0/1 в 1D цикл по w строго по убыванию.