0/1 рюкзак: почему при сжатии до 1D надо идти по весу справа налево?
Классический 0/1 рюкзак сжал до одномерного dp[w]. Но получаю неправильный ответ — предметы как будто берутся по нескольку раз. Вот цикл:
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; i++)
for (int w = wt[i]; w <= W; w++) // слева направо
dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
Где ошибка?
2 ответа
Направление обхода по w кодирует семантику задачи. В 0/1-рюкзаке dp[w] должно обновляться из значений предыдущего предмета (строки i-1). Когда ты идёшь слева направо, dp[w - wt[i]] для текущего предмета уже могло быть обновлено на этой же итерации i — то есть предмет i учтён повторно. Это превращает задачу в неограниченный рюкзак.
Для 0/1 нужно идти справа налево, тогда dp[w - wt[i]] ещё хранит значение без предмета i:
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; i++)
for (int w = W; w >= wt[i]; w--) // справа налево!
dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
Сложность O(n·W) по времени, O(W) по памяти. Запомни правило: 0/1 → убывающий цикл по весу, неограниченный → возрастающий. Это самая частая причина WA в рюкзаке.
Дополню мнемоникой. В возрастающем цикле dp[w - wt[i]] — это «уже с учётом предмета i», поэтому предмет можно класть снова и снова → unbounded. В убывающем — «ещё без предмета i» → каждый предмет максимум один раз. Один и тот же двумерный код dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt]+val) при сжатии до 1D просто требует, чтобы правый источник dp[w-wt] оставался от слоя i-1. Отсюда и направление.