0 1 Knapsack Problem in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of 0 1 Knapsack DP Table

What is the printed DP table after running the given 0 1 Knapsack code with weights = {1, 3, 4}, values = {10, 40, 50}, and capacity = 6?

DSA Java

public class Knapsack {
    public static void main(String[] args) {
        int[] weights = {1, 3, 4};
        int[] values = {10, 40, 50};
        int capacity = 6;
        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(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                System.out.print(dp[i][w] + " ");
            }
            System.out.println();
        }
    }
}

A [[0, 0, 0, 0, 0, 0, 0], [0, 10, 10, 10, 10, 10, 10], [0, 10, 10, 30, 40, 50, 50], [0, 10, 10, 40, 50, 60, 90]]

B [[0, 0, 0, 0, 0, 0, 0], [0, 10, 10, 10, 10, 10, 10], [0, 10, 10, 40, 40, 50, 50], [0, 10, 10, 40, 50, 60, 90]]

C [[0, 0, 0, 0, 0, 0, 0], [0, 10, 10, 10, 10, 10, 10], [0, 10, 10, 40, 50, 50, 50], [0, 10, 10, 40, 50, 60, 80]]

D [[0, 0, 0, 0, 0, 0, 0], [0, 10, 10, 10, 10, 10, 10], [0, 10, 10, 40, 50, 50, 50], [0, 10, 10, 40, 50, 60, 60]]

💡 Hint

Trace the DP table row by row, considering if the current item fits in the current capacity.

The DP table stores the maximum value achievable with the first i items and capacity w.

Row 1 considers only the first item (weight 1, value 10). It fills capacities >=1 with 10.

Row 2 adds the second item (weight 3, value 40), updating values where it improves the total.

Row 3 adds the third item (weight 4, value 50), further improving values where possible.

🧠 Conceptual

intermediate

Understanding 0 1 Knapsack Item Inclusion

In the 0 1 Knapsack problem, what does the decision to include or exclude an item depend on when filling the DP table?

A Whether the item's weight is less than the total number of items

B Whether including the item increases the total value without exceeding capacity

C Whether the item's value is greater than the sum of all previous items' values

D Whether the item has the smallest weight among all items

💡 Hint

Think about the goal of maximizing value without breaking the weight limit.

The DP table chooses to include an item only if it fits in the current capacity and improves the total value.

If including the item doesn't improve value or exceeds capacity, it is excluded.

🔧 Debug

advanced

Identify the Error in Knapsack Code

What error will this code produce when run? int[] weights = {2, 3}; int[] values = {20, 30}; int capacity = 4; 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(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]); } else { dp[i][w] = dp[i - 1][w]; } } }

A ArithmeticException

B NullPointerException

C ArrayIndexOutOfBoundsException

D No error, code runs correctly

💡 Hint

Check the size of the dp array and the indices used in the loops.

The dp array is declared with size n x (capacity+1), but the loops access dp[i][w] with i from 1 to n inclusive.

Since dp has only n rows (0 to n-1), accessing dp[n][w] causes ArrayIndexOutOfBoundsException.

🚀 Application

advanced

Maximum Value for Given Items and Capacity

Given weights = {2, 5, 1, 3}, values = {12, 20, 10, 15}, and capacity = 6, what is the maximum value achievable in the 0 1 Knapsack problem?

A 37

B 35

C 47

D 42

💡 Hint

Try combinations of items that fit within capacity and sum their values.

Possible combinations:

• Items 1,3,4: weights 2+1+3=6, values 12+10+15=37
• Items 2,3: weights 5+1=6, values 20+10=30
• Items 2,4: weights 5+3=8 (exceeds capacity)
• Items 1,4: weights 2+3=5, values 12+15=27

Maximum value is 37.

❓ Predict Output

expert

Output of Recursive 0 1 Knapsack with Memoization

What is the output printed by this Java code snippet for weights = {1, 2}, values = {10, 15}, capacity = 3?

DSA Java

import java.util.Arrays;
public class KnapsackMemo {
    static int[][] memo;
    public static int knapsack(int[] w, int[] v, int cap, int n) {
        if (n == 0 || cap == 0) return 0;
        if (memo[n][cap] != -1) return memo[n][cap];
        if (w[n - 1] > cap) {
            memo[n][cap] = knapsack(w, v, cap, n - 1);
        } else {
            memo[n][cap] = Math.max(knapsack(w, v, cap, n - 1), v[n - 1] + knapsack(w, v, cap - w[n - 1], n - 1));
        }
        return memo[n][cap];
    }
    public static void main(String[] args) {
        int[] weights = {1, 2};
        int[] values = {10, 15};
        int capacity = 3;
        int n = weights.length;
        memo = new int[n + 1][capacity + 1];
        for (int[] row : memo) Arrays.fill(row, -1);
        int result = knapsack(weights, values, capacity, n);
        System.out.println(result);
    }
}

A 25

B 15

C 10

D 20

💡 Hint

Consider all subsets of items that fit in capacity 3 and sum their values.

Items:

• Item 1: weight 1, value 10
• Item 2: weight 2, value 15

Capacity = 3

Possible combinations:

• Both items: weight 3, value 25
• Only item 2: weight 2, value 15
• Only item 1: weight 1, value 10

Maximum value is 25.

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