Knapsack Problem Overview

The knapsack problem involves selecting items with given weights and values to maximize total value within a weight cnostraint.

0/1 Knapsack

Given n items and a knapsack with maximum capacity w, where each item has a weight weight[i] and value value[i], determine which items to include to maximzie value. Each item can only be selected once.

A brute-force approach using backtracking results in exponential time complexity O(2^n), making dynamic programming necessary for efficient solutions.

Example: With a knapsack capacity of 4:

Two-Dimensional DP Implementation

1. State Definision: dp[i][j] represents the maximum value achievable using items from index 0 to i with a knapsack capacity of j.

2. Recurrence Relation:

   • If not including item i: dp[i][j] = dp[i-1][j]
   • If including item i: dp[i][j] = dp[i-1][j-weight[i]] + value[i]

   Therefore: dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

3. Initialization:

   • When capacity j = 0, all dp[i][0] = 0
   • For first item (i = 0):

     for (int j = 0; j < weight[0]; j++) {
         dp[0][j] = 0;
     }
     for (int j = weight[0]; j <= bagSize; j++) {
         dp[0][j] = value[0];
     }
     

4. Traversal Order:

   • Outer loop over items
   • Inner loop over capacities from 0 to bagSize

public class KnapsackSolver {
    public static void solveKnapsack(int[] weights, int[] values, int capacity) {
        int itemCount = weights.length;
        int[][] dp = new int[itemCount][capacity + 1];
        
        // Initialize first row
        for (int j = weights[0]; j <= capacity; j++) {
            dp[0][j] = values[0];
        }
        
        // Fill DP table
        for (int i = 1; i < itemCount; i++) {
            for (int j = 0; j <= capacity; j++) {
                if (j < weights[i]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weights[i]] + values[i]);
                }
            }
        }
        
        // Print result
        for (int i = 0; i < itemCount; i++) {
            for (int j = 0; j <= capacity; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println();
        }
    }
}

Space-Optimized One-Dimensional DP

Using a one-dimensional array reduces space complexity:

public static void optimizedKnapsack(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];
    
    for (int i = 0; i < weights.length; i++) {
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    
    for (int j = 0; j <= capacity; j++) {
        System.out.print(dp[j] + " ");
    }
}

Important note: Loop traversal order must be from high to low to avoid reusing the same item multiple times.

Subset Partition Problem

Given an array of positive integers, determine if it's possible to partition it into two subsets with equal sums.

This transforms into a subset sum problem where we check if a subset exists with sum equal to half the total sum.

class SubsetPartition {
    public boolean canSplit(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        if (totalSum % 2 != 0) return false;
        
        int target = totalSum / 2;
        int[] dp = new int[target + 1];
        
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
            
            if (dp[target] == target) return true;
        }
        
        return dp[target] == target;
    }
}

The key insight is that when the knapsack fills exactly to the target capacity, the partition is possible.