Why Unbounded Knapsack Problem in DSA Typescript?

The Big Idea

What if you could pack your bag perfectly without trying every single combination by hand?

The Scenario

Imagine you have a backpack and many types of items to pack. Each item has a weight and a value. You want to fill your backpack to get the highest total value. But you can take as many copies of each item as you want.

Trying to pick items one by one and checking all combinations by hand is like trying to solve a huge puzzle without a picture.

The Problem

Manually trying every combination of items is slow and confusing. You might miss better choices or waste time repeating the same checks. It's easy to make mistakes and hard to know if you found the best answer.

The Solution

The Unbounded Knapsack Problem uses a smart way to build up the best solution step by step. It remembers the best value for smaller weights and uses that to find the best for bigger weights. This saves time and avoids repeated work.

Before vs After

✗ Before

function maxValue(weights: number[], values: number[], capacity: number): number {
  // Try all combinations manually - very slow
  // No reuse of previous results
  return 0; // placeholder
}

✓ After

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

What It Enables

This approach lets you quickly find the best total value for any backpack size when you can use unlimited copies of items.

Real Life Example

Imagine a candy store where you can buy unlimited candies of different types. You want to fill your bag with candies to get the most sweetness without exceeding the bag's weight limit.

Key Takeaways

Manual checking of all item combinations is slow and error-prone.

Unbounded Knapsack uses dynamic programming to build solutions from smaller problems.

This method efficiently finds the best value when unlimited copies of items are allowed.