Knapsack Problems

The knapsack family asks how to pack items with weights and values into a limited capacity. This lesson covers 0/1 knapsack (each item once), subset sum / partition (LeetCode 416), space-optimized 1D DP, and links to unbounded knapsack — with C, Java, and Python code and output trace tables.

Overview

Knapsack problems differ by whether each item can be used once, unlimited times, or a bounded count.

0/1 Knapsack recurrence (max value):
  dp[i][w] = max(
      dp[i-1][w],                          // skip item i
      dp[i-1][w - weight[i]] + value[i]     // take item i (if fits)
  )
1D optimized: loop capacity W downward when processing each item

0/1 Knapsack — Max Value

Problem: Given weights, values, and capacity W, maximize total value without exceeding W. Each item at most once.

State: dp[w] = max value achievable with capacity exactly up to w (using items processed so far).

Complexity: O(n × W) time, O(W) space with 1D array.

0/1 Knapsack Code (C, Java, Python)

Python

def knapsack_01(weights, values, capacity):
    """0/1 knapsack — max value, each item used at most once. O(n × W)."""
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n):
        wt, val = weights[i], values[i]
        # Descending w: each item used at most once in 1D DP
        for w in range(capacity, wt - 1, -1):
            dp[w] = max(dp[w], dp[w - wt] + val)

    return dp[capacity]


if __name__ == "__main__":
    w, v, cap = [1, 2, 3], [6, 10, 12], 5
    print(f"weights={w}, values={v}, capacity={cap} → {knapsack_01(w, v, cap)}")
    # items 2+3 (wt 2+3=5, val 10+12=22)

Java

public class Knapsack01 {

    /** Max value 0/1 knapsack with 1D space optimization. */
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int[] dp = new int[capacity + 1];

        for (int i = 0; i < weights.length; i++) {
            int wt = weights[i], val = values[i];
            for (int w = capacity; w >= wt; w--) {
                dp[w] = Math.max(dp[w], dp[w - wt] + val);
            }
        }
        return dp[capacity];
    }

    public static void main(String[] args) {
        int[] w = {1, 2, 3}, v = {6, 10, 12};
        System.out.println(knapsack(w, v, 5));  // 22
    }
}

C

#include <stdio.h>

#define MAX_W 1000

/* 0/1 knapsack — return max value */
int knapsack_01(int weights[], int values[], int n, int capacity) {
    int dp[MAX_W + 1] = {0};
    int i, w, wt, val;

    for (i = 0; i < n; i++) {
        wt = weights[i];
        val = values[i];
        for (w = capacity; w >= wt; w--) {
            int candidate = dp[w - wt] + val;
            if (candidate > dp[w]) dp[w] = candidate;
        }
    }
    return dp[capacity];
}

int main(void) {
    int w[] = {1, 2, 3}, v[] = {6, 10, 12};
    printf("%d\n", knapsack_01(w, v, 3, 5));  /* 22 */
    return 0;
}

0/1 Knapsack Output & Trace

Program output

DP trace — capacity 0…5 after all items

Subset Sum & Partition

Partition Equal Subset Sum (LeetCode 416): Can array be split into two subsets with equal sum?

Equivalent to: does any subset sum to total / 2?

Recurrence: dp[s] = dp[s] OR dp[s − num] — boolean knapsack, each number once.

Subset Sum Code (C, Java, Python)

Python

def can_partition(nums):
    """LeetCode 416 — partition into two equal-sum subsets."""
    total = sum(nums)
    if total % 2 != 0:
        return False  # odd total → impossible

    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True  # sum 0 always reachable (empty subset)

    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] = dp[s] or dp[s - num]

    return dp[target]


if __name__ == "__main__":
    print(can_partition([1, 5, 11, 5]))   # True  (11 | 1+5+5)
    print(can_partition([1, 2, 3, 5]))    # False (total=11)

Java

public class SubsetSumPartition {

    public static boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 != 0) return false;

        int target = total / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int s = target; s >= num; s--) {
                dp[s] = dp[s] || dp[s - num];
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        System.out.println(canPartition(new int[]{1, 5, 11, 5}));  // true
        System.out.println(canPartition(new int[]{1, 2, 3, 5}));   // false
    }
}

C

#include <stdio.h>
#include <stdbool.h>

#define MAX_SUM 10000

bool can_partition(int nums[], int n) {
    int total = 0, i, num, s;
    for (i = 0; i < n; i++) total += nums[i];
    if (total % 2 != 0) return false;

    int target = total / 2;
    bool dp[MAX_SUM + 1] = {false};
    dp[0] = true;

    for (i = 0; i < n; i++) {
        num = nums[i];
        for (s = target; s >= num; s--) {
            if (dp[s - num]) dp[s] = true;
        }
    }
    return dp[target];
}

int main(void) {
    int a[] = {1, 5, 11, 5}, b[] = {1, 2, 3, 5};
    printf("%d\n", can_partition(a, 4));  /* 1 = true */
    printf("%d\n", can_partition(b, 4));  /* 0 = false */
    return 0;
}

Subset Sum Output & Trace

Program output

DP trace — nums = [1, 5, 11, 5], target = 11

Space Optimization

2D knapsack dp[i][w] can compress to 1D dp[w] when items are processed sequentially.

Knapsack Variants

More Examples

Example 1: 0/1 knapsack — no item fits together

Example 2: Partition — odd total

Example 3: Complexity

Approach Comparison

Real-Life Applications

Knapsack and subset-sum patterns appear whenever you have a fixed capacity and must pick a subset of items—each used at most once—to maximize value or reach an exact target.

Interview Tips

1. Ask: max value, exact sum, count ways, or partition?
2. Define dp[w] or dp[i][w] clearly before coding.
3. For 0/1, emphasize descending capacity loop in 1D form.
4. Subset sum: check odd total first for partition problems.
5. State pseudo-polynomial complexity O(n × W).
6. Connect unbounded variant to coin change.
7. Trace small example: 2 items, capacity 3, on whiteboard.