Unbounded Knapsack

01-23-2026

Description

Unbounded knapsack is a variation of 01 Knapsack where you can now use an item an infinite amount of times. To repeat the general idea of knapsack problems, we are trying to maximize or minimize or generally find some optimal selection of items, except now instead of choosing or excluding items in a binary sense, we can do as much or as little as we want. Note that this means we don't need or want to iterate backwards anymoreIn reference to the 0/1 knapsack implementation

How To Identify

The key characteristics of unbounded knapsack are similar to 0/1 Knapsack. We specifically look for:

  1. Dynamic Programming
  2. Constraints
  3. Items
  4. Can use an item any number of times.

General Template and Approach

One of the reasons that top competitive programmers are so good is that they can distinguish patterns and see similarities really well. This is no different here. Unbounded knapsack is essentially the same thing as 0/1 Knapsack implementation-wise:

python
dp = [float("inf")] * (size + 1)
dp[0] = 0
for i in items:
	for j in range(valid dp states):
		dp[i] = min(dp[i-j] + 1, dp[i])

return dp[target value]

Essentially the only difference is that you iterate forwards here, allowing items to reference and build upon themselves.

Solved Problems