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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of 0 1 Knapsack DP Table

What is the final maximum value stored in the DP table for the given items and capacity?

DSA Go

package main
import "fmt"
func knapsack(values, weights []int, capacity int) int {
 n := len(values)
 dp := make([][]int, n+1)
 for i := range dp {
  dp[i] = make([]int, capacity+1)
 }
 for i := 1; i <= n; i++ {
  for w := 1; w <= capacity; w++ {
   if weights[i-1] <= w {
    val1 := values[i-1] + dp[i-1][w-weights[i-1]]
    val2 := dp[i-1][w]
    if val1 > val2 {
     dp[i][w] = val1
    } else {
     dp[i][w] = val2
    }
   } else {
    dp[i][w] = dp[i-1][w]
   }
  }
 }
 return dp[n][capacity]
}
func main() {
 values := []int{60, 100, 120}
 weights := []int{10, 20, 30}
 capacity := 50
 fmt.Println(knapsack(values, weights, capacity))
}

A 200

B 180

C 160

D 220

💡 Hint

Think about which items fit best without exceeding capacity.

The maximum value is 220 by choosing items with weights 20 and 30 (values 100 + 120).

🧠 Conceptual

intermediate

Understanding 0 1 Knapsack Problem Constraints

Which statement correctly describes the 0 1 Knapsack problem?

A You can take fractional parts of items to maximize value.

B Each item can be taken at most once to maximize value within capacity.

C Each item can be taken multiple times to maximize value.

D Items must be taken in order without skipping any.

💡 Hint

Remember the meaning of '0 1' in the problem name.

In 0 1 Knapsack, each item is either taken or not taken once, no fractions or repeats.

🔧 Debug

advanced

Identify the Bug in Knapsack Implementation

What error does the following knapsack code produce when run?

DSA Go

func knapsack(values, weights []int, capacity int) int {
 n := len(values)
 dp := make([][]int, n)
 for i := range dp {
  dp[i] = make([]int, capacity+1)
 }
 for i := 1; i <= n; i++ {
  for w := 1; w <= capacity; w++ {
   if weights[i-1] <= w {
    val1 := values[i-1] + dp[i-1][w-weights[i-1]]
    val2 := dp[i-1][w]
    if val1 > val2 {
     dp[i][w] = val1
    } else {
     dp[i][w] = val2
    }
   } else {
    dp[i][w] = dp[i-1][w]
   }
  }
 }
 return dp[n-1][capacity]
}

A Returns incorrect maximum value

B Compilation error due to missing import

C Index out of range error

D No error, runs correctly

💡 Hint

Check how dp slice is created and accessed.

The dp slice is created with length n but accessed up to index n, causing out of range error.

🚀 Application

advanced

Number of Items Selected in Optimal Knapsack Solution

Given the items and capacity below, how many items are selected in the optimal solution?

DSA Go

values := []int{20, 5, 10, 40, 15, 25}
weights := []int{1, 2, 3, 8, 7, 4}
capacity := 10

A 4

B 3

C 2

D 5

💡 Hint

Trace which items fit best without exceeding capacity.

The optimal solution selects 4 items with total weight ≤ 10 and maximum value.

❓ Predict Output

expert

Output of Recursive Knapsack with Memoization

What is the output of the following Go code implementing recursive 0 1 Knapsack with memoization?

DSA Go

package main
import "fmt"
func knapsackRec(values, weights []int, capacity, n int, memo [][]int) int {
 if n == 0 || capacity == 0 {
  return 0
 }
 if memo[n][capacity] != -1 {
  return memo[n][capacity]
 }
 if weights[n-1] > capacity {
  memo[n][capacity] = knapsackRec(values, weights, capacity, n-1, memo)
 } else {
  val1 := values[n-1] + knapsackRec(values, weights, capacity-weights[n-1], n-1, memo)
  val2 := knapsackRec(values, weights, capacity, n-1, memo)
  if val1 > val2 {
   memo[n][capacity] = val1
  } else {
   memo[n][capacity] = val2
  }
 }
 return memo[n][capacity]
}
func main() {
 values := []int{24, 18, 18, 10}
 weights := []int{24, 10, 10, 7}
 capacity := 25
 n := len(values)
 memo := make([][]int, n+1)
 for i := range memo {
  memo[i] = make([]int, capacity+1)
  for j := range memo[i] {
   memo[i][j] = -1
  }
 }
 fmt.Println(knapsackRec(values, weights, capacity, n, memo))
}

A 28

B 42

C 34

D 24

💡 Hint

Consider which items fit best without exceeding capacity using recursion.

The maximum value is 28 by choosing items with weights 10 and 7 (values 18 + 10).

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 weight of items without exceeding the value limit

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

C. The number of items selected regardless of weight

D. The minimum weight of items selected

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 limit.

2. Step 2: Identify the constraint

   The constraint is the maximum weight capacity of the knapsack, so total weight must not exceed it.

3. Final Answer:

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

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 limit with value limit
• Thinking the problem maximizes number of items
• Ignoring the weight constraint

2. Which of the following Go code snippets correctly declares a 2D slice for dynamic programming in 0 1 Knapsack with capacity 'W' and 'n' items?

easy

A. dp := make([][]int, n+1); for i := range dp { dp[i] = make([]int, W+1) }

B. dp := make([]int, n+1, W+1)

C. dp := [][]int{n+1}{W+1}

D. dp := make([][]int, W+1); for i := range dp { dp[i] = make([]int, n+1) }"

Solution

1. Step 1: Understand 2D slice creation in Go

   To create a 2D slice, first create the outer slice with length n+1, then initialize each inner slice with length W+1.

2. Step 2: Check each option

   dp := make([][]int, n+1); for i := range dp { dp[i] = make([]int, W+1) } correctly creates dp with n+1 rows and W+1 columns. Options B and C have syntax errors or wrong types. dp := make([][]int, W+1); for i := range dp { dp[i] = make([]int, n+1) }" swaps dimensions incorrectly.

3. Final Answer:

   dp := make([][]int, n+1); for i := range dp { dp[i] = make([]int, W+1) } -> Option A

4. Quick Check:

   Correct 2D slice init = dp := make([][]int, n+1); for i := range dp { dp[i] = make([]int, W+1) } [OK]

Hint: Remember: outer slice length = items+1, inner = capacity+1 [OK]

Common Mistakes:

• Using make with wrong parameters
• Swapping rows and columns
• Trying to declare 2D slice in one step incorrectly

3. What is the output of the following Go code snippet for 0 1 Knapsack problem?

package main
import "fmt"
func main() {
  weights := []int{1, 3, 4}
  values := []int{10, 40, 50}
  W := 6
  n := len(weights)
  dp := make([][]int, n+1)
  for i := range dp {
    dp[i] = make([]int, W+1)
  }
  for i := 1; i <= n; i++ {
    for w := 1; w <= W; w++ {
      if weights[i-1] <= w {
        dp[i][w] = max(dp[i-1][w], values[i-1]+dp[i-1][w-weights[i-1]])
      } else {
        dp[i][w] = dp[i-1][w]
      }
    }
  }
  fmt.Println(dp[n][W])
}
func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}

medium

A. 80

B. 100

C. 90

D. 50

Solution

1. Step 1: Trace the DP table filling

   Items: (weight=1,value=10), (3,40), (4,50), capacity=6. Calculate max value for each capacity step by step.

2. Step 2: Calculate max value for capacity 6

   Choosing items 2 and 3 (weights 3+4=7) exceeds capacity, so best is items 1 and 3 (1+4=5) with value 10+50=60 or items 2 alone (40). But items 1 and 2 (1+3=4) value 10+40=50. Actually, best is items 2 and 3 separately or items 1 and 2 and 3? Check dp: max value at capacity 6 is 90 (items 2 and 3 combined is invalid, but items 1,2,3 combined weight 8 > 6). So best is items 2 and 3 separately or items 1 and 3 combined. The code outputs 90.

3. Final Answer:

   90 -> Option C

4. Quick Check:

   Max value for capacity 6 = 90 [OK]

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

Common Mistakes:

• Adding values without checking weight limit
• Confusing indices in dp array
• Forgetting to subtract weight when adding value

4. Find the error in this Go code snippet for 0 1 Knapsack DP and select the fix:

for i := 1; i <= n; i++ {
  for w := 1; w <= W; w++ {
    if weights[i] <= w {
      dp[i][w] = max(dp[i-1][w], values[i]+dp[i-1][w-weights[i]])
    } else {
      dp[i][w] = dp[i-1][w]
    }
  }
}

medium

A. Use weights[i-1] and values[i-1] instead of weights[i] and values[i]

B. Change loop to start from i := 0

C. Replace max function with min function

D. Remove else block

Solution

1. Step 1: Identify index error in array access

   Arrays weights and values are zero-indexed, but loop uses i starting from 1, so weights[i] and values[i] cause out-of-range or wrong access.

2. Step 2: Correct indexing for zero-based arrays

   Use weights[i-1] and values[i-1] to access correct elements corresponding to current item i.

3. Final Answer:

   Use weights[i-1] and values[i-1] instead of weights[i] and values[i] -> Option A

4. Quick Check:

   Fix indexing error = Use weights[i-1] and values[i-1] instead of weights[i] and values[i] [OK]

Hint: Remember Go slices start at index 0 [OK]

Common Mistakes:

• Using 1-based indexing on zero-based slices
• Ignoring out-of-range errors
• Changing loop start incorrectly

5. Given items with weights [2, 3, 5, 7] and values [1, 5, 2, 4], and knapsack capacity 10, which combination of items gives the maximum value using 0 1 Knapsack?

hard

A. Items with weights 5 and 7, total value 6

B. Items with weights 2, 3, and 5, total value 8

C. Items with weights 2 and 7, total value 5

D. Items with weights 3 and 7, total value 9

Solution

1. Step 1: Calculate total weights and values for each option

   Items with weights 3 and 7, total value 9: weights 3+7=10, values 5+4=9; Items with weights 2, 3, and 5, total value 8: 2+3+5=10, values 1+5+2=8; Items with weights 2 and 7, total value 5: 2+7=9, values 1+4=5; Items with weights 5 and 7, total value 6: 5+7=12 (exceeds capacity), invalid.

2. Step 2: Choose combination with max value under capacity

   Items with weights 3 and 7, total value 9 and B fit capacity 10, but Items with weights 3 and 7, total value 9 has higher value 9 vs 8. Items with weights 5 and 7, total value 6 exceeds capacity, Items with weights 2 and 7, total value 5 has lower value.

3. Final Answer:

   Items with weights 3 and 7, total value 9 -> Option D

4. Quick Check:

   Max value with capacity 10 = 9 [OK]

Hint: Sum weights and values, pick max value under capacity [OK]

Common Mistakes:

• Choosing items exceeding capacity
• Ignoring total value comparison
• Adding too many items without checking weight