Ограниченный рюкзак: как обработать k штук предмета быстрее O(n·k·W)?
В bounded knapsack у каждого предмета своё количество cnt[i]. Наивно я разворачиваю каждый предмет в cnt[i] копий и гоню обычный 0/1, но при больших cnt это O(W · Σcnt) и ловлю TLE. Есть стандартный приём, чтобы ускорить?
2 ответа
Да, это двоичная (бинарная) декомпозиция количества. Любое число cnt можно представить как сумму степеней двойки 1, 2, 4, ..., 2^(k-1) и остатка. Из этих «пакетов» комбинацией можно набрать любое количество от 0 до cnt. Вместо cnt копий получаешь O(log cnt) псевдопредметов, каждый со своим весом и ценностью, и гонишь обычный 0/1.
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; i++) {
int c = cnt[i];
for (int k = 1; c > 0; k <<= 1) {
int take = min(k, c); // последний пакет — остаток
c -= take;
int w = take * wt[i], v = take * val[i];
for (int j = W; j >= w; j--)
dp[j] = max(dp[j], dp[j - w] + v);
}
}
Сложность O(W · Σ log cnt[i]) по времени, O(W) по памяти. Грабля: пакеты должны идти 1, 2, 4, ..., а последний — это остаток c, а не очередная степень двойки, иначе суммы не покроют весь диапазон [0, cnt].
Альтернатива — оптимизация монотонной очередью за O(n·W). Для каждого предмета с весом w остатки W % w разбивают веса на классы, и внутри класса переход — это dp[j] = max(dp[j - t·w] + t·val) со скользящим максимумом, который держит deque за O(1) амортизированно. Это асимптотически лучше бинарной декомпозиции, но кода заметно больше и легко напортачить со знаком (надо хранить dp[j] - (j/w)·val, чтобы максимум был корректен). На практике двоичная декомпозиция проходит почти всегда, я бы начинал с неё.