Unbounded Knapsack Problem in DSA Typescript

Mental Model

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

Analogy: Imagine you have a backpack and unlimited candies of different sizes and tastiness. You want to fill your backpack to enjoy the most tastiness, 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 -> [0][1][2][3][4][5]
Values stored ->    [0][ ][ ][ ][ ][ ]

Dry Run Walkthrough

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

Goal: Find the maximum value we can get by filling the backpack with unlimited items without exceeding capacity 5

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

Capacity: 0 -> maxValue=0

Why: No space means no items can be added

Step 2: At capacity 1, try item with weight 1: value = 10 + maxValue at capacity 0 = 10

Capacity: 1 -> maxValue=10

Why: We can add one item of weight 1 for value 10

Step 3: At capacity 2, try item with weight 1 twice: value = 10 + maxValue at capacity 1 = 20

Capacity: 2 -> maxValue=20

Why: Using item weight 1 twice gives better value than others

Step 4: At capacity 3, try item weight 3: value = 40 + maxValue at capacity 0 = 40; also try item weight 1 thrice: 10 + maxValue at capacity 2 = 30; choose max 40

Capacity: 3 -> maxValue=40

Why: Item weight 3 gives better value than three times item weight 1

Step 5: At capacity 4, try item weight 4: value = 50 + maxValue at capacity 0 = 50; try item weight 3 + weight 1: 40 + maxValue at capacity 1 = 50; try item weight 1 four times: 10 + maxValue at capacity 3 = 50; max is 50

Capacity: 4 -> maxValue=50

Why: Multiple combinations give max value 50

Step 6: At capacity 5, try item weight 1 + capacity 4: 10 + 50 = 60; item weight 3 + capacity 2: 40 + 20 = 60; item weight 4 + capacity 1: 50 + 10 = 60; max is 60

Capacity: 5 -> maxValue=60

Why: Combining items multiple times yields max value 60

Result:

Capacity: 5 -> maxValue=60
Maximum value achievable: 60

Annotated Code

DSA Typescript

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

function unboundedKnapsack(items: Item[], capacity: number): number {
  const dp: number[] = new Array(capacity + 1).fill(0);

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

  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(items, capacity);
console.log(`Maximum value achievable: ${maxValue}`);

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

iterate through each capacity from 1 to max capacity

for (const item of items) {

check each item to see if it fits in current capacity

if (item.weight <= c) {

only consider items that fit in current capacity

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

update max value for capacity c by including current item multiple times

Output

Maximum value achievable: 60

Complexity Analysis

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

Space: O(capacity) because we store max values for each capacity in a single 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

max value is 0 because no items can fit

DSA Typescript

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

items array is empty

max value is 0 because no items to choose from

DSA Typescript

for (const item of items) {

item weight greater than capacity

item is skipped because it cannot fit

DSA Typescript

if (item.weight <= c) {

When to Use This Pattern

When you can use items unlimited times to maximize value within a capacity, reach for the unbounded knapsack pattern because it efficiently reuses items with dynamic programming.

Common Mistakes

Mistake: Treating unbounded knapsack like 0/1 knapsack by not allowing multiple uses of the same item
Fix: Use dp[c] = max(dp[c], item.value + dp[c - item.weight]) to allow repeated use of items

Summary

Find the maximum value achievable by using unlimited quantities of given items within a capacity.

Use when you can pick items multiple times to fill a capacity for maximum value.

The key is to build solutions for smaller capacities and reuse them to solve bigger capacities.

Practice

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

easy

A. In Unbounded Knapsack, you can use unlimited copies of each item.

B. In Unbounded Knapsack, items cannot be repeated.

C. Unbounded Knapsack only works with fractional items.

D. Unbounded Knapsack has a fixed number of items to choose from.

Solution

1. Step 1: Understand the item usage rules

   In 0/1 Knapsack, each item can be chosen at most once. In Unbounded Knapsack, items can be chosen unlimited times.

2. Step 2: Compare the problem constraints

   Unbounded Knapsack allows repeated use of the same item, unlike 0/1 Knapsack.

3. Final Answer:

   In Unbounded Knapsack, you can use unlimited copies of each item. -> Option A

4. Quick Check:

   Unlimited item usage = In Unbounded Knapsack, you can use unlimited copies of each item. [OK]

Hint: Unbounded means unlimited items allowed [OK]

Common Mistakes:

• Confusing unbounded with fractional knapsack
• Thinking items cannot repeat
• Assuming fixed item count

2. Which of the following TypeScript function signatures correctly represents the Unbounded Knapsack function?

easy

A. function unboundedKnapsack(W: number, wt: string[], val: number[], n: number): number

B. function unboundedKnapsack(W: string, wt: number[], val: number[], n: number): number

C. function unboundedKnapsack(W: number, wt: number[], val: number[], n: number): number

D. function unboundedKnapsack(W: number, wt: number[], val: number[], n: string): number

Solution

1. Step 1: Check parameter types for correctness

   Weight capacity W should be a number, weights wt and values val arrays of numbers, and n the number of items as a number.

2. Step 2: Identify the correct signature

   function unboundedKnapsack(W: number, wt: number[], val: number[], n: number): number matches all types correctly. Others have wrong types like string instead of number.

3. Final Answer:

   function unboundedKnapsack(W: number, wt: number[], val: number[], n: number): number -> Option C

4. Quick Check:

   Correct types for all parameters = function unboundedKnapsack(W: number, wt: number[], val: number[], n: number): number [OK]

Hint: Check parameter types carefully [OK]

Common Mistakes:

• Using string instead of number for weights or capacity
• Mixing array types
• Incorrect return type

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

const val = [10, 40, 50];
const wt = [1, 3, 4];
const W = 6;

function unboundedKnapsack(W: number, wt: number[], val: number[], n: number): number {
  const dp = Array(W + 1).fill(0);
  for (let i = 1; i <= W; i++) {
    for (let j = 0; j < n; j++) {
      if (wt[j] <= i) {
        dp[i] = Math.max(dp[i], dp[i - wt[j]] + val[j]);
      }
    }
  }
  return dp[W];
}

console.log(unboundedKnapsack(W, wt, val, val.length));

medium

A. 90

B. 100

C. 120

D. 80

Solution

1. Step 1: Understand the DP array construction

   We build dp array from 0 to W=6. For each capacity, we check all items and update dp[i] with max value including unlimited items.

2. Step 2: Calculate dp values step-by-step

   dp[1]=max(0, dp[0]+10)=10
   dp[2]=max(0, dp[1]+10)=20
   dp[3]=max(dp[3], dp[0]+40)=40, also dp[3]=max(40, dp[2]+10)=40
   dp[4]=max(dp[4], dp[1]+40)=50, also dp[4]=max(50, dp[0]+50)=50
   dp[5]=max(dp[5], dp[2]+40)=60, also dp[5]=max(60, dp[1]+50)=60
   dp[6]=max(dp[6], dp[3]+40)=80, also dp[6]=max(80, dp[2]+50)=90

3. Final Answer:

   90 -> Option A

4. Quick Check:

   Max value for W=6 = 90 [OK]

Hint: Build dp array incrementally for each capacity [OK]

Common Mistakes:

• Not considering multiple copies of items
• Incorrect dp array updates
• Mixing 0/1 and unbounded logic

4. Identify the bug in this Unbounded Knapsack TypeScript code snippet:

function unboundedKnapsack(W: number, wt: number[], val: number[], n: number): number {
  const dp = Array(W + 1).fill(0);
  for (let j = 0; j < n; j++) {
    for (let i = 1; i <= W; i++) {
      if (wt[j] <= i) {
        dp[i] = Math.max(dp[i], dp[i - wt[j]] + val[j]);
      }
    }
  }
  return dp[W];
}

medium

A. The condition wt[j] <= i should be wt[j] < i

B. Initialization of dp array is incorrect

C. Return statement should be dp[0] instead of dp[W]

D. Loops are reversed; inner loop should be over items, outer over capacity

Solution

1. Step 1: Analyze loop order for unbounded knapsack

   For unbounded knapsack, outer loop should iterate over capacities (i), inner loop over items (j) to allow multiple uses of items.

2. Step 2: Identify the bug in loop order

   Here, outer loop is over items and inner over capacity, which is incorrect and leads to wrong results.

3. Final Answer:

   Loops are reversed; inner loop should be over items, outer over capacity -> Option D

4. Quick Check:

   Correct loop order = capacity outer, items inner [OK]

Hint: Outer loop on capacity for unbounded knapsack [OK]

Common Mistakes:

• Swapping loop order
• Wrong dp initialization
• Incorrect return index

5. Given items with values val = [5, 10, 15] and weights wt = [1, 3, 4], and a knapsack capacity W = 7, what is the maximum value achievable using the Unbounded Knapsack approach?

hard

A. 25

B. 30

C. 35

D. 40

Solution

1. Step 1: Calculate dp array values for capacities 1 to 7

   dp[0]=0
   dp[1]=max(0, dp[0]+5)=5
   dp[2]=max(0, dp[1]+5)=10
   dp[3]=max(dp[3], dp[0]+10)=10, also dp[3]=max(10, dp[2]+5)=10
   dp[4]=max(dp[4], dp[1]+10)=15, also dp[4]=max(15, dp[0]+15)=15
   dp[5]=max(dp[5], dp[2]+10)=20, also dp[5]=max(20, dp[1]+15)=20
   dp[6]=max(dp[6], dp[3]+10)=20, also dp[6]=max(20, dp[2]+15)=25
   dp[7]=max(dp[7], dp[4]+10)=25, also dp[7]=max(25, dp[3]+15)=25

2. Step 2: Find maximum value at capacity 7

   The maximum value achievable is 25, but check if better combinations exist:
   Try dp[7] = dp[3] + val[2] = 10 + 15 = 25
   Try dp[7] = dp[4] + val[1] = 15 + 10 = 25
   Try dp[7] = dp[6] + val[0] = 25 + 5 = 30 (better)
   Update dp[7] = 30
   Try dp[7] = dp[3] + val[2] = 10 + 15 = 25 (less than 30)
   So final dp[7] = 30

3. Final Answer:

   30 -> Option B

4. Quick Check:

   Maximum value for W=7 = 30 [OK]

Hint: Check all item combinations for each capacity [OK]

Common Mistakes:

• Ignoring multiple item usage
• Stopping at first max value found
• Not updating dp array correctly