Неограниченный рюкзак vs число способов: один цикл, а ответы про разное — почему?
Заметил, что код неограниченного рюкзака (макс ценность) и код «числа способов набрать сумму» структурно совпадают — оба идут возрастающим циклом по объёму. Но один считает max, другой — сумму. Это случайность или за этим стоит общая идея?
2 ответа
Это не случайность — оба построены на возрастающем цикле по объёму, который разрешает использовать предмет/номинал многократно. Разница только в операции агрегации над переходами:
// неограниченный рюкзак: макс ценность
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]);
// число способов набрать сумму (комбинации): сумма путей
vector<long long> ways(W + 1, 0); ways[0] = 1;
for (int i = 0; i < n; i++)
for (int w = wt[i]; w <= W; w++)
ways[w] += ways[w - wt[i]];
Оба — это ДП на DAG состояний, где ребро ведёт w-wt[i] → w. «Макс ценность» = самый дорогой путь, «число способов» = число путей. Возрастающий цикл с внешним циклом по предметам гарантирует: каждый предмет «доступен бесконечно» (unbounded), и при этом для способов считаются именно комбинации (без дублей по порядку). Сложность обеих O(n·W). База разная: для max dp[0]=0, для способов ways[0]=1 (один пустой способ).
Полезно увидеть это как полукольцо: одна и та же структура переходов, меняешь только (операцию объединения, операцию композиции, нейтральные элементы). Для max-ценности: (max, +, -inf, 0). Для числа способов: (+, ×коэф, 0, 1). Для «существует ли способ» (boolean subset sum): (OR, AND, false, true). Поэтому если умеешь один шаблон рюкзака — остальные получаются заменой агрегатора. Главное не перепутать базу: нейтральный элемент операции объединения (inf/0/false) и единицу композиции (0/1/true).