0 1 Knapsack Problem in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the '0 1' in the 0 1 Knapsack Problem mean?

It means each item can either be taken completely (1) or not taken at all (0). You cannot take fractional parts of an item.

beginner

What is the main goal of the 0 1 Knapsack Problem?

To maximize the total value of items put into the knapsack without exceeding its weight capacity.

intermediate

In the dynamic programming solution of 0 1 Knapsack, what does the DP table represent?

Each cell dp[i][w] represents the maximum value achievable using the first i items with a weight limit w.

intermediate

Why can't greedy algorithms solve the 0 1 Knapsack Problem optimally?

Because choosing items based on value or weight ratio alone may miss the combination that yields the maximum total value.

intermediate

What is the time complexity of the classic dynamic programming solution for the 0 1 Knapsack Problem?

O(n * W), where n is the number of items and W is the maximum weight capacity of the knapsack.

In the 0 1 Knapsack Problem, what does the '1' signify?

A You can take fractional parts of items

B You can take only one unit of each item

C You can take unlimited quantities of each item

D You must take all items

The '1' means each item can be taken at most once, so only one unit of each item is allowed.

Which approach is commonly used to solve the 0 1 Knapsack Problem optimally?

A Greedy algorithm

B Brute force without memoization

C Dynamic programming

D Divide and conquer

Dynamic programming efficiently solves the problem by storing intermediate results to avoid repeated work.

What does dp[i][w] represent in the 0 1 Knapsack DP solution?

A Maximum value using first i items with weight limit w

B Minimum weight to achieve value w using i items

C Number of items used to reach weight w

D Total weight of first i items

dp[i][w] stores the best value achievable with the first i items and weight capacity w.

What is the main constraint in the 0 1 Knapsack Problem?

A Total weight must not exceed capacity

B Total value must be less than capacity

C Number of items must be less than capacity

D All items must be included

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

Why is the greedy approach not suitable for the 0 1 Knapsack Problem?

A It is too slow

B It ignores the weight limit

C It always finds the optimal solution

D It may miss better combinations by choosing locally best items first

Greedy picks the best item at each step but may miss combinations that yield higher total value.

Explain how dynamic programming solves the 0 1 Knapsack Problem step-by-step.

Think about building solutions from smaller subproblems.

Describe why fractional items are not allowed in the 0 1 Knapsack Problem and how that changes the solution approach.

Compare with fractional knapsack problem.

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