0-1 Knapsack Problem with Rolling Array Optimization

Understanding the Problem

The 0-1 knapsack problem is a classic optimization challenge where we aim to maximize the value of items placed in a knapsack with a fixed capacity. Each item can either be included (1) or not included (0), hence the name 0-1 knapsack.

Standard 2D Dynamic Programming Approach

The conventional solution uses a two-dimensional array to store intermediate results. The state dp[i][j] represents the maximum value achievable with the first i items and a knapsack capacity of j.

#include <iostream>
#include <vector>
#include <algorithm>

const int MAX_CAPACITY = 1010;
const int MAX_ITEMS = 1010;

int main() {
    int itemCount, knapsackCapacity;
    std::cin >> itemCount >> knapsackCapacity;
    
    std::vector<int> volumes(itemCount + 1);
    std::vector<int> values(itemCount + 1);
    std::vector dp(itemCount + 1, std::vector<int>(knapsackCapacity + 1, 0));
    
    for (int i = 1; i <= itemCount; i++) {
        std::cin >> volumes[i] >> values[i];
    }
    
    for (int i = 1; i <= itemCount; i++) {
        for (int j = 1; j <= knapsackCapacity; j++) {
            if (j >= volumes[i]) {
                dp[i][j] = std::max(dp[i-1][j], values[i] + dp[i-1][j-volumes[i]]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    
    std::cout << dp[itemCount][knapsackCapacity] << std::endl;
    return 0;
}

Optimization with Rolling Arrays

Observing the 2D approach, we notice that each state dp[i][j] only depends on the previous row dp[i-1][j]. This insight allows us to optimize space complexity by using a single-dimensional array and updating it in reverse order.

Key Insight

Instead of maintaining a full 2D array, we can use a 1D array where dp[j] represents the maximum value achievable with the current items and capacity j. By iterating backwards through the capacities, we ensure we don't overwrite values needed for subsequent calculations.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>

const int MAX_CAPACITY = 10010;

int main() {
    int itemCount, knapsackCapacity;
    std::cin >> itemCount >> knapsackCapacity;
    
    std::vector<int> volumes(itemCount);
    std::vector<int> values(itemCount);
    std::vector<int> dp(knapsackCapacity + 1, 0);
    
    for (int i = 0; i < itemCount; i++) {
        std::cin >> volumes[i] >> values[i];
    }
    
    for (int i = 0; i < itemCount; i++) {
        for (int j = knapsackCapacity; j >= volumes[i]; j--) {
            dp[j] = std::max(dp[j], dp[j - volumes[i]] + values[i]);
        }
    }
    
    std::cout << dp[knapsackCapacity] << std::endl;
    return 0;
}

Why Reverse Iteration?

The reverse iteration is crucial for the correctness of the optimized solution. If we iterate forward, we might use the updated values within the same iteration, effectively allowing multiple uses of the same item (which violates the 0-1 knapsack constraint). By iterating backwards, we ensure each item is only considered once.

Complexity Comparison

Approach	Time Complexity	Space Complexity
2D DP	O(n × w)	O(n × w)
1D DP (Rolling Array)	O(n × w)	O(w)

The rolling array optimization significantly reduces space complexity while maintaining the same time complexity, making it particularly useful for problems with large capacity constraints.