Unbounded Knapsack Problem in DSA Javascript - Time & Space Complexity

Time Complexity: Unbounded Knapsack Problem

O(n * m)

Understanding Time Complexity

We want to understand how the time needed to solve the Unbounded Knapsack problem grows as the input size changes.

Specifically, how does the number of items and the knapsack capacity affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function unboundedKnapsack(capacity, weights, values) {
  const dp = Array(capacity + 1).fill(0);
  for (let c = 1; c <= capacity; c++) {
    for (let i = 0; i < weights.length; i++) {
      if (weights[i] <= c) {
        dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
      }
    }
  }
  return dp[capacity];
}
    

This code finds the maximum value achievable with unlimited items and a given knapsack capacity.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops: outer loop runs over capacities from 1 to capacity, inner loop runs over all items.
• How many times: Outer loop runs capacity times, inner loop runs number of items times for each capacity.

How Execution Grows With Input

As capacity or number of items grow, the total operations grow by multiplying these two.

Input Size (capacity n, items m)	Approx. Operations
n=10, m=5	10 * 5 = 50
n=100, m=5	100 * 5 = 500
n=1000, m=5	1000 * 5 = 5000

Pattern observation: Operations grow linearly with capacity and number of items multiplied together.

Final Time Complexity

Time Complexity: O(n * m)

This means the time needed grows proportionally to the product of knapsack capacity and number of items.

Common Mistake

[X] Wrong: "The time complexity is exponential because we can pick unlimited items repeatedly."

[OK] Correct: The dynamic programming approach avoids repeated work by storing results, so it only does a fixed number of operations based on capacity and items.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming improves efficiency over naive recursion, a key skill in problem solving.

Self-Check

"What if we changed the problem to 0/1 Knapsack (each item only once)? How would the time complexity change?"

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