Unbounded Knapsack Problem in DSA Javascript - Build from Scratch

Unbounded Knapsack Problem

📖 Scenario: You are helping a shop owner decide how to fill a knapsack with items to maximize value. The shop owner can take unlimited quantities of each item.Each item has a weight and a value. The knapsack has a maximum weight capacity.

🎯 Goal: Build a program that calculates the maximum total value the shop owner can carry in the knapsack using the unbounded knapsack approach.

📋 What You'll Learn

Create arrays for item weights and values with exact values

Create a variable for the knapsack capacity

Use a dynamic programming approach to solve the unbounded knapsack problem

Print the maximum value that fits in the knapsack

💡 Why This Matters

🌍 Real World

This problem models situations where you can use unlimited quantities of resources to maximize profit or value, such as packing goods, cutting rods, or resource allocation.

💼 Career

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

1

Create item weights and values arrays

Create an array called weights with these exact values: 1, 3, 4, 5. Also create an array called values with these exact values: 10, 40, 50, 70.

DSA Javascript

# Your code here

Hint

Use const weights = [1, 3, 4, 5]; and const values = [10, 40, 50, 70];

2

Set the knapsack capacity

Create a variable called capacity and set it to 8.

DSA Javascript

const weights = [1, 3, 4, 5];
const values = [10, 40, 50, 70];
# Your code here

Hint

Use const capacity = 8; to set the knapsack capacity.

3

Calculate maximum value using unbounded knapsack logic

Create an array called dp of length capacity + 1 filled with zeros. Use a for loop with variable w from 1 to capacity. Inside it, use another for loop with variable i from 0 to weights.length - 1. If weights[i] is less than or equal to w, update dp[w] to the maximum of its current value and values[i] + dp[w - weights[i]].

DSA Javascript

const weights = [1, 3, 4, 5];
const values = [10, 40, 50, 70];
const capacity = 8;
# Your code here

Hint

Use dynamic programming with nested loops to fill the dp array.

4

Print the maximum value that fits in the knapsack

Print the value of dp[capacity] using console.log(dp[capacity]).

DSA Javascript

const weights = [1, 3, 4, 5];
const values = [10, 40, 50, 70];
const capacity = 8;

const dp = new Array(capacity + 1).fill(0);
for (let w = 1; w <= capacity; w++) {
    for (let i = 0; i < weights.length; i++) {
        if (weights[i] <= w) {
            dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }
}
# Your code here

Hint

Use console.log(dp[capacity]) to print the result.

Practice

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

easy

A. Unbounded Knapsack uses recursion while 0/1 Knapsack uses iteration

B. In Unbounded Knapsack each item can be chosen any number of times; in 0/1 each item is chosen at most once

C. Unbounded Knapsack has no weight constraint

D. 0/1 Knapsack allows fractional items while Unbounded does not

Solution

1. Step 1: Understand 0/1 constraint

   In 0/1 Knapsack each item has a binary choice - include once or exclude. After including, it cannot be reused.

2. Step 2: Understand Unbounded constraint

   In Unbounded Knapsack there is no limit on how many times an item can be selected. The same item can fill the bag.

3. Step 3: Practical impact

   This changes the recurrence: 0/1 uses dp[i-1][w-wt] (previous row); Unbounded uses dp[i][w-wt] (same row, enabling reuse).

4. Final Answer:

   Unbounded allows unlimited item repetition. -> Option B

5. Quick Check:

   Unbounded = unlimited copies. 0/1 = at most one per item. [OK]

Hint: Unbounded = unlimited copies. 0/1 = at most one copy per item. [OK]

Common Mistakes:

• Confusing Unbounded with Fractional Knapsack
• Thinking 0/1 allows unlimited items
• Believing recursion vs iteration distinguishes them

2. In the 1D bottom-up Unbounded Knapsack solution, why does the inner loop go left-to-right (from weight[i] to W)?

medium

A. Left-to-right is faster in JavaScript due to array caching

B. Left-to-right allows the same item to be reused in one pass - exactly what Unbounded Knapsack requires

C. Right-to-left would cause negative indices

D. Left-to-right matches the order of the items array

Solution

1. Step 1: Left-to-right reuse

   Computing dp[w] using dp[w - weight[i]] left-to-right means dp[w - weight[i]] has already been updated - it reflects using item i again. This is intentional reuse.

2. Step 2: Contrast with 0/1

   0/1 Knapsack goes right-to-left to prevent reuse - ensuring dp[w - weight[i]] holds the pre-item value.

3. Final Answer:

   Left-to-right enables intentional item reuse. -> Option B

4. Quick Check:

   Left-to-right = reuse. Right-to-left = no reuse. [OK]

Hint: Left-to-right = reuse allowed (Unbounded). Right-to-left = no reuse (0/1). [OK]

Common Mistakes:

• Thinking direction affects performance not semantics
• Not knowing left-to-right enables reuse
• Confusing with 0/1 which requires right-to-left

3. Given items with weights [1, 3, 4] and values [10, 40, 50] and capacity W=6, what is the maximum value for Unbounded Knapsack?

medium

A. 60

B. 80

C. 90

D. 100

Solution

1. Step 1: Try repeating each item

   Item 1 (w=1, v=10) × 6 = value 60. Item 2 (w=3, v=40) × 2 = value 80, weight=6 exactly. Item 3 (w=4, v=50) + item 1 × 2 = value 70.

2. Step 2: Find maximum

   Two copies of item 2 gives value 80 using exactly capacity 6 - this is the maximum.

3. Final Answer:

   80 -> Option B

4. Quick Check:

   Item 2 × 2: 40×2=80, weight 3×2=6. [OK]

Hint: Try repeating each item to fill capacity: item 2 twice (3×2=6, 40×2=80) wins. [OK]

Common Mistakes:

• Only trying single-item combinations
• Not trying repeated use of the same item
• Confusing with 0/1 where each item used at most once

4. What is the time and space complexity of the optimized 1D Unbounded Knapsack solution?

medium

A. Time O(n×W), Space O(n×W)

B. Time O(2^n), Space O(n)

C. Time O(n×W), Space O(W)

D. Time O(n log W), Space O(W)

Solution

1. Step 1: Time complexity

   Two nested loops - n items × W+1 capacities. Each cell O(1). Total O(n×W).

2. Step 2: Space complexity

   Only a 1D array dp[W+1] is needed, updated in place. Space O(W).

3. Step 3: Contrast with 2D

   Standard 2D DP uses O(n×W) space. 1D optimization reduces to O(W).

4. Final Answer:

   Time O(n×W), Space O(W) -> Option C

5. Quick Check:

   1D = O(n×W) time, O(W) space. [OK]

Hint: 1D Unbounded = O(n×W) time, O(W) space - one array updated in place. [OK]

Common Mistakes:

• Reporting O(n×W) space for 1D version
• Confusing with O(2^n) exponential recursion
• Forgetting 1D reduces space to O(W)

5. Which real-world problem is a direct application of Unbounded Knapsack?

hard

A. Job scheduling where each job can be done only once

B. Coin change - finding minimum coins to make an amount where each denomination can be used unlimited times

C. Activity selection where activities have deadlines

D. Matrix chain multiplication to minimize operations

Solution

1. Step 1: Map coin change to Knapsack

   Coin denominations = item weights. Target amount = capacity W. Each denomination usable unlimited times = Unbounded constraint.

2. Step 2: Rule out other options

   Job scheduling once per job = 0/1 Knapsack. Activity selection = greedy. Matrix chain = interval DP.

3. Final Answer:

   Coin change with unlimited denominations. -> Option B

4. Quick Check:

   Coin change = Unbounded. Coins used unlimited times, amount = capacity. [OK]

Hint: Coin change = Unbounded Knapsack. Each coin denomination reusable, amount is capacity. [OK]

Common Mistakes:

• Mapping job scheduling to Unbounded instead of 0/1
• Not recognizing coin change as Knapsack
• Thinking activity selection uses Unbounded DP