Subset sum на n=40: почему meet-in-the-middle, а не обычное ДП?
Есть n чисел (n ≤ 40), каждое до 10^9. Надо узнать, можно ли набрать подмножество с суммой ровно S (S тоже большое). Обычное subset-sum ДП по сумме не лезет — сумма до 4·10^10, массив dp[S] не выделить. Перебор всех 2^40 тоже не пройдёт. Что делать?
2 ответа
Когда сумма огромная, но n маленькое (≤ 40), классическое ДП dp[sum] по значению суммы неприменимо — память и время зависят от величины суммы, а не от n. Здесь работает meet in the middle: дели массив на две половины по ~n/2, в каждой перебираешь все 2^(n/2) подмножеств и собираешь их суммы. Для левой половины кладёшь суммы в отсортированный массив, для правой — для каждой суммы s ищешь бинпоиском, есть ли в левой части S - s.
vector<long long> gen(vector<long long>& v) {
int k = v.size();
vector<long long> res;
for (int mask = 0; mask < (1 << k); mask++) {
long long s = 0;
for (int i = 0; i < k; i++) if (mask & (1 << i)) s += v[i];
res.push_back(s);
}
return res;
}
// L = gen(left), R = gen(right); sort(R);
bool ok = false;
for (long long s : L)
if (binary_search(R.begin(), R.end(), S - s)) { ok = true; break; }
Сложность O(2^(n/2) · n/2) по времени, O(2^(n/2)) по памяти. Для n=40 это ~2^20 ≈ 10^6 на половину — мгновенно. Грабли: суммы кладём в long long (40·10^9 переполнит int), и аккуратно с границей S - s (тоже long long).
Ориентир, когда какой подход: если значения/сумма малы (S ≤ ~10^6), бери ДП по сумме за O(n·S) — оно проще. Если n мало (≤ 40), но суммы большие — meet in the middle за O(2^(n/2)). Если оба велики — задача, скорее всего, не про чистый subset sum, ищи другую структуру. Не пытайся натянуть dp[S] на гигантскую S — это типичная ловушка, ведущая к MLE.