Understanding the unbounded knapsack problem

Unlike the 0/1 knapsack problem, many real-world optimization problems allow the same option to be used an unlimited number of times rather than restricting each choice to a single use. In these situations, the decision is not simply whether to include an option or not, but how many times it should be chosen while still respecting the overall capacity constraints. Each option has an associated cost and value, and the objective is to determine the combination that maximizes total value without exceeding the available capacity.

A fundamental problem in this space is the unbounded knapsack problem, where "unbounded" means that each item can be included an unlimited number of times.

The unbounded knapsack problem extends beyond simple one-time selections and proves essential in scenarios like currency denomination (making change with unlimited coins of each type), rod cutting problems (cutting rods or materials where the same length can be cut repeatedly), production planning (manufacturing items with unlimited raw materials), and resource allocation where the same type of resource can be deployed multiple times.

In this lesson, we will learn about the unbounded knapsack problem and how it can be solved efficiently using a dynamic programming solution.

The unbounded knapsack problem

Consider we are given n types of items, where the item at index i has a weight weights[i] and a value values[i]. We also have a knapsack with a maximum weight capacity capacity. Unlike the 0/1 variant, each item can be included zero, one, or multiple times in the knapsack.