Unbounded Knapsack Problem in DSA Javascript

Mental Model

You want to fill a bag with items to get the most value, and you can use each item as many times as you want.

Analogy: Imagine you have a backpack and unlimited candies of different sizes and tastiness. You want to fill your backpack to enjoy the tastiest candies possible, and you can pick any candy multiple times.

Capacity: 5
Items: [weight: 1, value: 10], [weight: 3, value: 40], [weight: 4, value: 50]

Backpack capacity -> [5]
Items -> (1,10), (3,40), (4,50)

Dry Run Walkthrough

Input: capacity = 5, items = [(weight=1, value=10), (weight=3, value=40), (weight=4, value=50)]

Goal: Find the maximum value we can get by filling the backpack with these items, using any item multiple times.

Step 1: Start with capacity 0, max value is 0 because no space

dp[0] = 0

Why: No capacity means no items can be added

Step 2: For capacity 1, try each item: only item with weight 1 fits, value 10

dp[1] = 10

Why: Only item 1 fits, so max value is 10

Step 3: For capacity 2, try items: item 1 twice (10+10=20), others don't fit

dp[2] = 20

Why: Using item 1 twice gives max value 20

Step 4: For capacity 3, try items: item 3 fits once (value 40), or item 1 thrice (30), max is 40

dp[3] = 40

Why: Item 3 alone is better than three item 1s

Step 5: For capacity 4, try items: item 4 once (50), item 3 + item 1 (40+10=50), item 1 four times (40), max is 50

dp[4] = 50

Why: Best value is 50 using item 4 or item 3 + item 1

Step 6: For capacity 5, try items: item 4 + item 1 (50+10=60), item 3 + item 1 twice (40+20=60), item 1 five times (50), max is 60

dp[5] = 60

Why: Best value is 60 using item 4 + item 1 or item 3 + item 1 twice

Result:

dp array: [0, 10, 20, 40, 50, 60]
Maximum value for capacity 5 is 60

Annotated Code

DSA Javascript

class Item {
  constructor(weight, value) {
    this.weight = weight;
    this.value = value;
  }
}

function unboundedKnapsack(capacity, items) {
  const dp = new Array(capacity + 1).fill(0);

  for (let w = 1; w <= capacity; w++) {
    for (const item of items) {
      if (item.weight <= w) {
        dp[w] = Math.max(dp[w], dp[w - item.weight] + item.value);
      }
    }
  }

  return dp[capacity];
}

// Driver code
const items = [new Item(1, 10), new Item(3, 40), new Item(4, 50)];
const capacity = 5;
const maxValue = unboundedKnapsack(capacity, items);
console.log(`Maximum value for capacity ${capacity} is ${maxValue}`);

for (let w = 1; w <= capacity; w++) {

Iterate over each capacity from 1 to max capacity

for (const item of items) {

Check each item for current capacity

if (item.weight <= w) {

Only consider items that fit in current capacity

dp[w] = Math.max(dp[w], dp[w - item.weight] + item.value);

Update max value for capacity w by including current item multiple times

Output

Maximum value for capacity 5 is 60

Complexity Analysis

Time: O(n * capacity) because we check all items for each capacity from 1 to capacity

Space: O(capacity) because we store max values for each capacity in dp array

vs Alternative: Compared to 0/1 knapsack which only allows one use per item, unbounded knapsack reuses items, but complexity remains similar with dynamic programming

Edge Cases

capacity = 0

Returns 0 because no items can fit

DSA Javascript

for (let w = 1; w <= capacity; w++) {

items array empty

Returns 0 because no items to choose from

DSA Javascript

for (const item of items) {

items with weight greater than capacity

Those items are ignored since they don't fit

DSA Javascript

if (item.weight <= w) {

When to Use This Pattern

When you can use items multiple times to fill a capacity for max value, reach for unbounded knapsack pattern because it handles unlimited item reuse efficiently.

Common Mistakes

Mistake: Treating unbounded knapsack like 0/1 knapsack and not allowing multiple uses of the same item
Fix: Use dp[w - item.weight] + item.value to allow repeated use of items

Summary

Finds the max value to fill a capacity using unlimited copies of given items.

Use when items can be chosen multiple times to maximize value within capacity.

The key is to build solutions for all capacities by reusing previous results allowing repeated items.

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