01 Knapsack

Problem Statement

Given N items and a knapsack with capacity m, each item has a volume v[i] and value w[i]. Each item can be selected at most once. Determine which items to select so that the total volume does not exceed the knapsack's capacity and the total value is maximized.

Approach

Let dp[i][j] denote the maximum value achievable using the first i items with a knapsack capacity of j.

The recurrence relation is:

dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])

Since only the previous row affects current computations, we can optimize space by using a single array:

dp[j] = max(dp[j], dp[j - v[i]] + w[i])

To ensure each item is used only once, iterate backwards over capacities:

for (int i = 1; i <= n; ++i)
    for (int j = m; j >= v[i]; --j)
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

Complete Knapsack

Problem Statement

Same setup as above, but each item can be seelcted multiple times.

Approach

Use forward iteration instead of bakcward iteration to allow unlimited usage:

dp[j] = max(dp[j], dp[j - v[i]] + w[i])

for (int i = 1; i <= n; ++i)
    for (int j = v[i]; j <= m; ++j)
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

Multiple Knapsack

Problem Statement

Each item can be selected up to c[i] times.

Naive Approach

Expand each item into c[i] copies and solve using 01 knapsack:

dp[i][j] = max(dp[i][j - k * v[i]] + k * w[i]) for 0 <= k <= c[i]

Optimized with Monotonic Queue

Group states based on remainder modulo v[i]. For a fixed remainder r, compute values of form r + x * v[i] where x ranges continuously.

Maintain a deque to efficiently query maximum within sliding window:

for (int i = 1; i <= n; ++i, b ^= 1)
    for (int r = 0; r < v[i]; ++r)
    {
        while (!q.empty()) q.pop_back();
        for (int k = 0; k <= m / v[i]; ++k)
        {
            while (!q.empty() && q.front() < k - c[i]) q.pop_front();
            while (!q.empty() && dp[b^1][r + q.back() * v[i]] + (k - q.back()) * w[i] < dp[b^1][r + k * v[i]])
                q.pop_back();
            q.push_back(k);
            dp[b][r + k * v[i]] = dp[b^1][r + q.front() * v[i]] + (k - q.front()) * w[i];
        }
    }

Grouped Knapsack

Problem Statement

Items belong to groups, and at most one item per group can be chosen.

Approach

For each group, perform a 01 knapsack on its items:

for (int k = 1; k <= groups; ++k)
    for (int i = m; i >= 0; --i)
        for (int j = 1; j <= count[k]; ++j)
            if (i >= volume[group_items[k][j]])
                dp[i] = max(dp[i], dp[i - volume[group_items[k][j]]] + cost[group_items[k][j]]);

Minimum Lexicographical Solution

Problem Statement

Find the lexicographically smallest set of items that achieves the maximum value.

Approach

Track the source of each state in an auxiliary array path. Iterate from last item to first to maintain lexicographical order:

for (int i = n; i >= 1; --i)
{
    for (int j = 0; j < v[i]; ++j)
    {
        dp[i][j] = dp[i+1][j];
        path[i][j] = path[i+1][j];
    }
    for (int j = v[i]; j <= m; ++j)
    {
        if (dp[i+1][j] > dp[i+1][j - v[i]] + w[i])
        {
            dp[i][j] = dp[i+1][j];
            path[i][j] = path[i+1][j];
        }
        else
        {
            dp[i][j] = dp[i+1][j - v[i]] + w[i];
            path[i][j] = i;
        }
    }
}