Core Principles of the 0-1 Knapsack Problem

The 0-1 Knapsack Problem serves as the foundation for various packing challenges. Given a set of items with specific weights and values, the objective is to maximize value while not exceeding a given capacity constraint. Each item can be included at most once.

Dynamic Programming Solution

We use a DP table where dp[i][capacity] represents the maximum value achievable by selecting from the first i items without exceeding the given capacity. The recurrence relation is:

dp[i][cap] = max(
    dp[i-1][cap],  // Excluding current item
    dp[i-1][cap - weights[i-1]] + values[i-1]  // Including current item
)

Initialization and Iteration

Initialize the DP table with zeros. For the first item, set values for capacities equal to or greater than its weight:

vector<vector<int>> dp(items_count, vector<int>(max_capacity + 1, 0));
for (int cap = item_weights[0]; cap <= max_capacity; cap++) {
    dp[0][cap] = item_values[0];
}

The solution can be computed through either item-first or capacity-first iteration:

for (int i = 1; i < items_count; i++) {
    for (int cap = 0; cap <= max_capacity; cap++) {
        if (cap < item_weights[i]) {
            dp[i][cap] = dp[i-1][cap];
        } else {
            dp[i][cap] = max(dp[i-1][cap], 
                            dp[i-1][cap - item_weights[i]] + item_values[i]);
        }
    }
}

Space-Optimized Implementasion

We can reduce space complexity using a single-dimensional array by processing items in reverse capacity order:

vector<int> optimized(max_capacity + 1, 0);
for (int i = 0; i < items_count; i++) {
    for (int cap = max_capacity; cap >= item_weights[i]; cap--) {
        optimized[cap] = max(optimized[cap], 
                            optimized[cap - item_weights[i]] + item_values[i]);
    }
}

Solving Partition Equal Subset Sum

The partition problem requires checking if an array can be divided into two subsets with equal sums. We approach this as a knapsack challenge where we seek a subset summing to half the total.

Algorithm Implementation

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        if (total % 2 != 0) return false;
        
        int target = total / 2;
        vector<int> dp(target + 1, 0);
        
        for (int num : nums) {
            for (int cap = target; cap >= num; cap--) {
                dp[cap] = max(dp[cap], dp[cap - num] + num);
            }
        }
        
        return dp[target] == target;
    }
};

The solution checks whether we can exactly fill a "knapsack" of size target using array elements as both weights and values.