The Multiple Knapsack Problem

Given n types of items, where type i has c_i copies, value v_i, and weight w_i. We need to select items to maximize the total value in a knapsack with maximum capacity m.

Solution 1

One approach is to transform the multiple knapsack problem into a 0-1 knapsack problem. The naive method would be to split each item type into c_i individual items, but this results in O(∑c_i·m) time complexity, which is inefficient.

Instead, we can use a binary decomposition approach. Consider the problem of representing numbers in a range [0, x] using the minimum number of values. We can select powers of 2 (1, 2, 4, ..., 2^(k-1)) to represent any number up to 2^k - 1. For the range [0, x], we can use powers of 2 up to 2^floor(log₂(x+1)) - 1, and add (x - 2^floor(log₂(x+1)) + 1) to cover the remaining range.

Applying this to the multiple knapsack problem, each item type i can be decomposed into:

• (2^0·v_i, 2^0·w_i)
• (2^1·v_i, 2^1·w_i)
• ...
• (2^(floor(log₂(c_i+1))-1)·v_i, 2^(floor(log₂(c_i+1))-1)·w_i)
• ((c_i - 2^floor(log₂(c_i+1)) + 1)·v_i, (c_i - 2^floor(log₂(c_i+1)) + 1)·w_i)

This allows us to represent any quantity from 0 to c_i of item type i using O(log c_i) items. After decomposition, we apply the standard 0-1 knapsack algorithm, achieving O(∑log c_i·m) time complexity and O(∑log c_i + m) space complexity.

Here's the implementation:

int newItemCount; // Number of new items after decomposition
int newValues[MAX_ITEMS * LOG_COUNT + 1]; // Values of decomposed items
int newWeights[MAX_ITEMS * LOG_COUNT + 1]; // Weights of decomposed items
int dp[MAX_CAPACITY + 1];

newItemCount = 0;
for (int i = 0; i < itemCount; i++) {
    int logCount = log2(itemCounts[i] + 1);
    // Add binary components
    for (int j = 0; j < logCount; j++) {
        newValues[++newItemCount] = itemValues[i] << j;
        newWeights[newItemCount] = itemWeights[i] << j;
    }
    // Add remainder if needed
    if (itemCounts[i] > (1 << logCount) - 1) {
        newValues[++newItemCount] = itemValues[i] * (itemCounts[i] - (1 << logCount) + 1);
        newWeights[newItemCount] = itemWeights[i] * (itemCounts[i] - (1 << logCount) + 1);
    }
}

memset(dp, 0, sizeof(dp));
for (int i = 1; i <= newItemCount; i++) {
    for (int j = maxCapacity; j >= newWeights[i]; j--) {
        dp[j] = max(dp[j], dp[j - newWeights[i]] + newValues[i]);
    }
}
// Result is dp[maxCapacity]

Solution 2

We can also solve this directly using dynamic programming. Let dp[i][j] represent the maximum value achievable with the first i item types and remaining capacity j. The recurrence relation is:

dp[i][j] = max{dp[i-1][j-k·w_i] + k·v_i} for k from 0 to min(c_i, j/w_i)

This can be optimized using a monotonic queue. By rewriting the equation and separating variables, we get:

dp[i][j] = max{(w_i·dp[i-1][k] - k·v_i + j·v_i)/w_i}

for k in [max(0, j-c_i·w_i), j] where k ≡ j (mod w_i)

We process states in groups based on modulo w_i, maintaining a monotonic queue for each group to find the optimal solution efficiently. This approach runs in O(n·m) time and O(m) space with a rolling array optimization.

Here's the implementation:

int queue[MAX_CAPACITY]; // Monotonic queue
int dp[2][MAX_CAPACITY + 1]; // Using rolling array

memset(dp, 0, sizeof(dp));
for (int i = 0; i < itemCount; i++) {
    for (int j = 0; j < itemWeights[i]; j++) {
        int front = 0, rear = 0; // Queue pointers
        for (int k = j; k <= maxCapacity; k += itemWeights[i]) {
            // Remove elements outside the valid range
            while (front < rear && queue[front] < k - itemCounts[i] * itemWeights[i]) {
                front++;
            }
            // Maintain monotonic property
            while (front < rear && 
                   itemWeights[i] * dp[(i-1)&1][queue[rear-1]] - queue[rear-1] * itemValues[i] <= 
                   itemWeights[i] * dp[(i-1)&1][k] - k * itemValues[i]) {
                rear--;
            }
            queue[rear++] = k; // Add current element to queue
            // Calculate dp using optimal value from queue
            dp[i&1][k] = (itemWeights[i] * dp[(i-1)&1][queue[front]] - 
                         queue[front] * itemValues[i] + k * itemValues[i]) / itemWeights[i];
        }
    }
}
// Result is dp[(itemCount-1)&1][maxCapacity]

Comparison of Soluitons

Solution 2 has better time and space complexity than Solution 1. However, the monotonic queue approach is more complex to derive and implement. In competitive programming where time limits are lenient, Solution 1 might be preferable for its simplicity.