Learn
Unbounded Knapsack
The Unbounded Knapsack problem is a classic DP problem where you maximize value given a weight capacity, with unlimited copies of each item available. It's also known as the "complete knapsack" problem.
You have item types with weights and values. You can use each type unlimited times. Your goal is to maximize value without exceeding capacity .
You define as the maximum value achievable with capacity . For each capacity, you try adding each item type and take the best result.
function unboundedKnapsack(W, weights, values, n):
dp = array of size W + 1, initialized to 0
for w from 1 to W:
for i from 0 to n - 1:
if weights[i] <= w:
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
Since items are unlimited, your depends on from the same row. You iterate forward through capacities, allowing the same item to be picked multiple times.
Applications: You use unbounded knapsack for coin change problems, rod cutting, and resource allocation where items can be reused.
Time complexity: because you check all items for each capacity up to .
Space complexity: for the D DP array.