0 1 Knapsack Problem in DSA Java

Mental Model

We want to pick items with values and weights to maximize value without exceeding weight limit. Each item can be chosen only once.

Analogy: Imagine packing a backpack for a trip. You have limited space and many items with different importance and sizes. You want to pack the most valuable combination without overloading.

Knapsack capacity: 5
Items:
[Item0: weight=2, value=3]
[Item1: weight=3, value=4]
[Item2: weight=4, value=5]

Table rows = items considered
Table columns = weight limits from 0 to capacity

DP Table (initial):
  W 0 1 2 3 4 5
I0 0 0 0 0 0 0
I1 0 0 0 0 0 0
I2 0 0 0 0 0 0

Dry Run Walkthrough

Input: items: [(weight=2, value=3), (weight=3, value=4), (weight=4, value=5)], capacity=5

Goal: Find max value we can carry without exceeding capacity 5, choosing each item at most once

Step 1: Consider item 0 (weight=2, value=3), fill dp for weights 0 to 5

DP Table:
  W 0 1 2 3 4 5
I0 0 0 3 3 3 3
I1 0 0 0 0 0 0
I2 0 0 0 0 0 0

Why: We can only take item 0 if capacity >= 2, so values updated from weight 2 onwards

Step 2: Consider item 1 (weight=3, value=4), update dp using previous row

DP Table:
  W 0 1 2 3 4 5
I0 0 0 3 3 3 3
I1 0 0 3 4 4 7
I2 0 0 0 0 0 0

Why: At weight 3, choose max of not taking item 1 (3) or taking it (4). At weight 5, taking both items 0 and 1 gives value 7

Step 3: Consider item 2 (weight=4, value=5), update dp using previous row

DP Table:
  W 0 1 2 3 4 5
I0 0 0 3 3 3 3
I1 0 0 3 4 4 7
I2 0 0 3 4 5 7

Why: At weight 4, taking item 2 alone gives value 5 which is better than previous 3 or 4. At weight 5, max remains 7 from previous best

Result:

DP Table final:
  W 0 1 2 3 4 5
I0 0 0 3 3 3 3
I1 0 0 3 4 4 7
I2 0 0 3 4 5 7

Maximum value achievable: 7

Annotated Code

DSA Java

public class Knapsack01 {
    // Item class to hold weight and value
    static class Item {
        int weight, value;
        Item(int w, int v) {
            weight = w;
            value = v;
        }
    }

    // Function to solve 0 1 Knapsack problem
    public static int knapsack(Item[] items, int capacity) {
        int n = items.length;
        int[][] dp = new int[n + 1][capacity + 1];

        // Build dp table row by row
        for (int i = 1; i <= n; i++) {
            Item curr = items[i - 1];
            for (int w = 0; w <= capacity; w++) {
                if (curr.weight > w) {
                    dp[i][w] = dp[i - 1][w]; // can't take current item
                } else {
                    // max of not taking or taking current item
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - curr.weight] + curr.value);
                }
            }
        }
        return dp[n][capacity];
    }

    public static void main(String[] args) {
        Item[] items = {
            new Item(2, 3),
            new Item(3, 4),
            new Item(4, 5)
        };
        int capacity = 5;
        int maxValue = knapsack(items, capacity);
        System.out.println("Maximum value achievable: " + maxValue);
    }
}

for (int i = 1; i <= n; i++) {

iterate over items to build dp table row by row

for (int w = 0; w <= capacity; w++) {

iterate over all weight capacities from 0 to max capacity

if (curr.weight > w) { dp[i][w] = dp[i - 1][w]; }

if current item weight exceeds capacity w, skip item

dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - curr.weight] + curr.value);

choose max between not taking or taking current item

Output

Maximum value achievable: 7

Complexity Analysis

Time: O(n * capacity) because we fill a table with n rows and capacity+1 columns once

Space: O(n * capacity) because we store results for each item and capacity combination

vs Alternative: Compared to brute force exponential approach, DP reduces time drastically by storing subproblem results

Edge Cases

No items

Returns 0 because no value can be taken

DSA Java

for (int i = 1; i <= n; i++) {

Capacity zero

Returns 0 because no weight can be carried

DSA Java

for (int w = 0; w <= capacity; w++) {

Item weight greater than capacity

Item is skipped and dp value copied from previous row

DSA Java

if (curr.weight > w) { dp[i][w] = dp[i - 1][w]; }

When to Use This Pattern

When you need to pick items with weights and values to maximize value without exceeding capacity, and each item can be chosen once, reach for 0 1 Knapsack DP pattern.

Common Mistakes

Mistake: Using the same item multiple times by not referencing previous row in dp
Fix: Always use dp[i-1][...] when deciding to take or skip current item to ensure single use

Mistake: Not initializing dp table properly causing wrong base cases
Fix: Initialize dp with zeros and start loops from i=1 and w=0 to handle base cases correctly

Summary

Find the maximum value of items that fit in a knapsack without exceeding capacity, choosing each item once.

Use when you have limited capacity and must decide which items to include for max value.

The key is building a table that stores best values for subproblems of items and capacities.

Practice

1. What does the 0 1 Knapsack Problem aim to maximize given a set of items with weights and values?

easy

A. The total value of items without exceeding the weight limit

B. The total weight of items regardless of value

C. The number of items selected

D. The minimum weight of selected items

Solution

1. Step 1: Understand the problem goal

   The 0 1 Knapsack Problem tries to select items to maximize total value without exceeding the weight capacity.

2. Step 2: Identify the constraint

   The total weight of selected items must not exceed the knapsack's capacity.

3. Final Answer:

   The total value of items without exceeding the weight limit -> Option A

4. Quick Check:

   Maximize value under weight limit = The total value of items without exceeding the weight limit [OK]

Hint: Focus on maximizing value, not weight or count [OK]

Common Mistakes:

• Confusing weight maximization with value maximization
• Ignoring the weight limit constraint
• Thinking the problem counts items instead of values

2. Which of the following is the correct way to declare the DP array for the 0 1 Knapsack Problem in Java?

easy

A. int[] dp = new int[n+1];

B. int[][] dp = new int[n+1][W+1];

C. int[][] dp = new int[W+1][n+1];

D. int dp = new int[n+1][W+1];

Solution

1. Step 1: Understand DP array dimensions

   We use a 2D array with rows for items (n+1) and columns for weight capacities (W+1).

2. Step 2: Check Java syntax for 2D array

   Correct syntax is int[][] dp = new int[n+1][W+1];

3. Final Answer:

   int[][] dp = new int[n+1][W+1]; -> Option B

4. Quick Check:

   2D array with items and weights = int[][] dp = new int[n+1][W+1]; [OK]

Hint: DP array rows = items+1, columns = capacity+1 [OK]

Common Mistakes:

• Using 1D array instead of 2D
• Swapping dimensions incorrectly
• Wrong Java syntax for array declaration

3. What is the output of the following Java code snippet for 0 1 Knapsack with weights = {1, 3, 4}, values = {10, 40, 50}, capacity = 7?

int[] weights = {1, 3, 4};
int[] values = {10, 40, 50};
int capacity = 7;
int n = weights.length;
int[][] dp = new int[n+1][capacity+1];
for (int i = 1; i <= n; i++) {
  for (int w = 1; w <= capacity; w++) {
    if (weights[i-1] <= w) {
      dp[i][w] = Math.max(values[i-1] + dp[i-1][w - weights[i-1]], dp[i-1][w]);
    } else {
      dp[i][w] = dp[i-1][w];
    }
  }
}
System.out.println(dp[n][capacity]);

medium

A. 80

B. 100

C. 90

D. 50

Solution

1. Step 1: Fill DP table for each item and capacity

   Key values: - Item 1 (w=1, v=10): dp[1][1..7] = 10 - Item 2 (w=3, v=40): dp[2][1..2]=10, dp[2][3]=40, dp[2][4..7]=50 - Item 3 (w=4, v=50): dp[3][1..2]=10, dp[3][3]=40, dp[3][4]=50, dp[3][5..6]=60, dp[3][7]=90 (max(50 + dp[2][3]=90, 50))

2. Step 2: Find maximum value at dp[n][capacity]

   dp[3][7] = 90 (select items 2 and 3: 40 + 50 = 90, weights 3+4=7)

3. Final Answer:

   90 -> Option C

4. Quick Check:

   Max value for capacity 7 = 90 [OK]

Hint: Trace DP table row by row for each item [OK]

Common Mistakes:

• Adding values without checking weight limit
• Confusing indices in arrays
• Forgetting to consider previous dp values

4. Identify the error in this Java code snippet for 0 1 Knapsack and select the fix:

int[] weights = {2, 3, 4};
int[] values = {3, 4, 5};
int capacity = 5;
int n = weights.length;
int[][] dp = new int[n][capacity+1];
for (int i = 1; i <= n; i++) {
  for (int w = 1; w <= capacity; w++) {
    if (weights[i-1] <= w) {
      dp[i][w] = Math.max(values[i-1] + dp[i-1][w - weights[i-1]], dp[i-1][w]);
    } else {
      dp[i][w] = dp[i-1][w];
    }
  }
}

medium

A. Change dp array size to int[n+1][capacity+1]

B. Change loop to start from i = 0

C. Use dp[i][w-1] instead of dp[i-1][w]

D. Remove the if condition inside the loop

Solution

1. Step 1: Check dp array size and indexing

   dp is declared as int[n][capacity+1], but loops use i from 1 to n, accessing dp[i], which causes ArrayIndexOutOfBoundsException.

2. Step 2: Fix dp size to match loop indices

   Declare dp as int[n+1][capacity+1] to allow indexing from 0 to n safely.

3. Final Answer:

   Change dp array size to int[n+1][capacity+1] -> Option A

4. Quick Check:

   Array size must match loop indices [OK]

Hint: DP size = items+1 rows to avoid index errors [OK]

Common Mistakes:

• Using dp size smaller than loop range
• Starting loop from 0 but indexing from 1
• Ignoring array index exceptions

5. Given items with weights = {2, 3, 5, 7}, values = {1, 5, 2, 4}, and capacity = 10, what is the maximum value achievable using 0 1 Knapsack? Also, which items are selected?

hard

A. Maximum value 6; items with weights 7 and 2 selected

B. Maximum value 7; items with weights 2, 3, and 5 selected

C. Maximum value 9; items with weights 3, 5, and 2 selected

D. Maximum value 9; items with weights 3 and 7 selected

Solution

1. Step 1: Calculate maximum value using DP

   Check combinations: - Items 3 and 7 weights sum to 10, values 5 + 4 = 9 (3 weight item value is 5, 7 weight item value is 4) - Items 2,3,5 weights sum to 10, values 1+5+2=8 - Items 3 and 7 give 9 value, better than others - Items 2 and 7 sum weight 9, values 1+4=5 Maximum value is 9 with items 3 and 7.

2. Step 2: Verify selected items

   Selected items are weights 3 and 7 with values 5 and 4 respectively.

3. Final Answer:

   Maximum value 9; items with weights 3 and 7 selected -> Option D

4. Quick Check:

   Max value 9 with weights 3+7 = 10 capacity [OK]

Hint: Check all combinations fitting capacity for max value [OK]

Common Mistakes:

• Adding values without checking total weight
• Selecting items exceeding capacity
• Confusing item weights and values