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.