Unbounded Knapsack Problem in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the dp array with zeros for the knapsack capacity.

DSA Javascript

const dp = new Array(capacity + 1).fill([1]);

Drag options to blanks, or click blank then click option'

Anull

B0

Cundefined

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using null or undefined instead of 0 causes incorrect calculations.

We fill the dp array with 0 because initially, the maximum value for any capacity is zero.

2fill in blank

medium

Complete the code to loop through all capacities from 1 to the given capacity.

DSA Javascript

for (let w = 1; w <= [1]; w++) {

Drag options to blanks, or click blank then click option'

Acapacity

Bweights.length

Cvalues.length

DmaxWeight

Attempts:

3 left

💡 Hint

Common Mistakes

Using weights.length or values.length instead of capacity.

We loop from 1 to capacity to fill dp for all sub-capacities.

3fill in blank

hard

Fix the error in the condition to check if the current item can fit in the knapsack.

DSA Javascript

if (weights[i] [1] w) {

Drag options to blanks, or click blank then click option'

A<=

B>

C==

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using > or < causes wrong logic for fitting items.

The item weight must be less than or equal to the current capacity to fit.

4fill in blank

hard

Fill both blanks to update dp[w] with the maximum value including the current item.

DSA Javascript

dp[w] = Math.max(dp[w], dp[w - [1]] + [2]);

Drag options to blanks, or click blank then click option'

Aweights[i]

Bvalues[i]

Cweights[w]

Dvalues[w]

Attempts:

3 left

💡 Hint

Common Mistakes

Using weights[w] or values[w] instead of weights[i] and values[i].

We subtract the item's weight from current capacity and add its value to dp.

5fill in blank

hard

Fill all three blanks to complete the unbounded knapsack function.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

Aweights

Bvalues

Cweights.length

Dcapacity.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using capacity.length instead of weights.length for loop limit.

The function takes weights and values arrays and capacity. The inner loop runs for all items using weights.length.

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