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]