Unbounded Knapsack Problem in DSA Go - Build from Scratch

Unbounded Knapsack Problem

📖 Scenario: You are packing items into a bag to maximize value. You can take unlimited quantities of each item.Each item has a weight and a value. The bag has a weight limit.

🎯 Goal: Build a program that finds the maximum total value you can carry in the bag without exceeding the weight limit, using the unbounded knapsack approach.

📋 What You'll Learn

Create slices for item weights and values

Create an integer variable for the bag capacity

Use a slice to store maximum values for each weight capacity

Implement the unbounded knapsack logic using loops

Print the maximum value for the full bag capacity

💡 Why This Matters

🌍 Real World

This problem models packing or resource allocation where you can use unlimited quantities of items, like cutting raw materials or filling containers.

💼 Career

Understanding dynamic programming and knapsack problems is important for software engineers working on optimization, logistics, and algorithm design.

1

Create item weights and values slices

Create two slices called weights and values with these exact entries: weights = []int{1, 3, 4} and values = []int{15, 50, 60}

DSA Go

# Create slices weights and values with given entries
# Your code here

Hint

Use Go slice syntax with exact values for weights and values.

2

Set the bag capacity

Add an integer variable called capacity and set it to 8

DSA Go

package main

func main() {
    weights := []int{1, 3, 4}
    values := []int{15, 50, 60}
    // Set capacity to 8
    // Your code here
}

Hint

Use a simple integer variable for capacity.

3

Implement unbounded knapsack logic

Create a slice called dp of length capacity+1 with all zeros. Use a for loop with variable w from 1 to capacity inclusive. Inside it, use another for loop with variable i from 0 to len(weights)-1. If weights[i] <= w, update dp[w] to the maximum of dp[w] and dp[w - weights[i]] + values[i].

DSA Go

package main

func main() {
    weights := []int{1, 3, 4}
    values := []int{15, 50, 60}
    capacity := 8
    // Create dp slice and implement unbounded knapsack loops
    // Your code here
}

Hint

Use nested loops and update dp slice for each weight capacity.

4

Print the maximum value for the full capacity

Add a fmt.Println statement to print dp[capacity]

DSA Go

package main

import "fmt"

func main() {
    weights := []int{1, 3, 4}
    values := []int{15, 50, 60}
    capacity := 8

    dp := make([]int, capacity+1)

    for w := 1; w  dp[w] {
                    dp[w] = val
                }
            }
        }
    }

    // Print the maximum value for capacity
    // Your code here
}

Hint

Print the last element of dp slice which holds the answer.

Practice

1. What is the main difference between the Unbounded Knapsack Problem and the 0/1 Knapsack Problem?

easy

A. 0/1 Knapsack allows fractional items, Unbounded Knapsack does not.

B. Unbounded Knapsack uses a different weight limit than 0/1 Knapsack.

C. In Unbounded Knapsack, items can be chosen unlimited times; in 0/1 Knapsack, each item can be chosen only once.

D. Unbounded Knapsack always has fewer items than 0/1 Knapsack.

Solution

1. Step 1: Understand item selection rules

   In 0/1 Knapsack, each item can be selected at most once. In Unbounded Knapsack, items can be selected multiple times without limit.

2. Step 2: Compare problem constraints

   The key difference is the repetition allowance of items, which changes the approach to solving the problem.

3. Final Answer:

   In Unbounded Knapsack, items can be chosen unlimited times; in 0/1 Knapsack, each item can be chosen only once. -> Option C

4. Quick Check:

   Item repetition rule differs = A [OK]

Hint: Remember: Unbounded means unlimited item picks [OK]

Common Mistakes:

• Confusing item repetition rules
• Thinking 0/1 Knapsack allows multiple picks
• Mixing fractional knapsack with unbounded knapsack

2. Which of the following Go code snippets correctly initializes the DP array for solving the Unbounded Knapsack problem with capacity W?

easy

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

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

C. dp := make([]int, W-1)

D. dp := make([]int, W*2)

Solution

1. Step 1: Understand DP array size requirement

   The DP array stores maximum values for capacities from 0 to W inclusive, so it needs length W+1.

2. Step 2: Check Go slice initialization

   Using make([]int, W+1) creates a slice of length W+1, which covers all capacities including zero.

3. Final Answer:

   dp := make([]int, W+1) -> Option A

4. Quick Check:

   DP array length = W+1 [OK]

Hint: DP array size = capacity + 1 for zero indexing [OK]

Common Mistakes:

• Using dp size W instead of W+1
• Using negative or zero size slices
• Confusing capacity with number of items

3. What will be the output of the following Go code snippet for Unbounded Knapsack?

package main
import "fmt"
func unboundedKnapsack(W int, wt []int, val []int) int {
    dp := make([]int, W+1)
    for i := 0; i <= W; i++ {
        for j := 0; j < len(wt); j++ {
            if wt[j] <= i {
                if dp[i] < dp[i-wt[j]] + val[j] {
                    dp[i] = dp[i-wt[j]] + val[j]
                }
            }
        }
    }
    return dp[W]
}
func main() {
    W := 5
    wt := []int{1, 3, 4}
    val := []int{10, 40, 50}
    fmt.Println(unboundedKnapsack(W, wt, val))
}

medium

A. 90

B. 100

C. 50

D. 80

Solution

1. Step 1: Trace DP array updates for capacity 5

   Calculate max value for each capacity: - i=1: max(dp[1], dp[0]+10)=10 - i=2: max(dp[2], dp[1]+10)=20 - i=3: max(dp[3], dp[0]+40, dp[2]+10)=40 - i=4: max(dp[4], dp[1]+40, dp[0]+50)=50 - i=5: max(dp[5], dp[2]+40, dp[1]+50)=90

2. Step 2: Final DP value at capacity 5

   dp[5] = 90, which is the maximum value achievable with unlimited items.

3. Final Answer:

   90 -> Option A

4. Quick Check:

   Max value at W=5 is 90 [OK]

Hint: Check dp updates for each capacity step [OK]

Common Mistakes:

• Ignoring multiple item picks
• Using 0/1 knapsack logic
• Incorrect dp array indexing

4. Identify the bug in the following Go code snippet for Unbounded Knapsack and select the correct fix:

func unboundedKnapsack(W int, wt []int, val []int) int {
    dp := make([]int, W)
    for i := 1; i <= W; i++ {
        for j := 0; j < len(wt); j++ {
            if wt[j] <= i {
                dp[i] = max(dp[i], dp[i-wt[j]] + val[j])
            }
        }
    }
    return dp[W]
}

medium

A. Change dp size to W and loop i from 0 to W-1

B. Change dp size to W-1 and loop i from 1 to W-1

C. Initialize dp with zeros and keep code as is

D. Change dp size to W+1 and loop i from 0 to W inclusive

Solution

1. Step 1: Check dp slice size and indexing

   dp is created with size W, but code accesses dp[W], which is out of range. Also, dp should cover 0 to W inclusive, so size must be W+1.

2. Step 2: Adjust loop range and dp size

   Loop i should start from 0 or 1 and go up to W inclusive. dp size must be W+1 to avoid index errors.

3. Final Answer:

   Change dp size to W+1 and loop i from 0 to W inclusive -> Option D

4. Quick Check:

   dp size = W+1 and loop i ≤ W [OK]

Hint: dp array must cover all capacities including zero [OK]

Common Mistakes:

• Using dp size W but accessing dp[W]
• Looping beyond dp slice length
• Not initializing dp correctly

5. Given items with weights wt = [2, 3, 5] and values val = [50, 70, 100], and a knapsack capacity W = 8, what is the maximum value achievable using the Unbounded Knapsack approach?

hard

A. 200

B. 270

C. 250

D. 220

Solution

1. Step 1: Calculate max values for capacities up to 8

   Calculate dp array stepwise: - i=0: 0 - i=1: 0 (no item fits) - i=2: max(0, dp[0]+50)=50 - i=3: max(0, dp[0]+70)=70 - i=4: max(dp[4], dp[2]+50)=100 - i=5: max(dp[5], dp[0]+100, dp[3]+50)=120 - i=6: max(dp[6], dp[4]+50, dp[3]+70)=170 - i=7: max(dp[7], dp[5]+50, dp[4]+70)=190 - i=8: max(dp[8], dp[6]+50, dp[5]+70, dp[3]+100)=270

2. Step 2: Identify maximum value at capacity 8

   dp[8] = 270 is the highest value achievable with unlimited items.

3. Final Answer:

   270 -> Option B

4. Quick Check:

   Max value at W=8 is 270 [OK]

Hint: Build dp array stepwise considering all items [OK]

Common Mistakes:

• Not considering multiple picks of same item
• Calculating dp values incorrectly
• Ignoring smaller capacity combinations