Understanding the bounded knapsack problem

In many real-world applications, software must make decisions under limited resources while also dealing with the limited availability of each option. In such situations, an item may not be restricted to a single choice but may also not be available an unlimited number of times. Instead, each item type may be selected multiple times up to a specified limit. Just like the regular 0/1 knapsack problem, each option provides some benefit, but selecting it consumes part of the available budget and may prevent other options from being chosen. The goal, therefore, is to determine which combination of options produces the greatest overall value without exceeding the given constraint.

A fundamental problem in this space is the bounded knapsack problem, which extends the classic knapsack framework to scenarios where items come in limited quantities.

The bounded knapsack problem mirrors real-world situations more accurately than the 0/1 variant, a few examples of which are: managing inventory where each product has limited stock, allocating bandwidth across multiple connection types with capacity constraints, loading containers with batches of goods, or selecting investments where each opportunity has a maximum investment limit.

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

The bounded knapsack problem

Consider we are given n item types, where the item at index i has a weight weights[i], a value values[i], and a count counts[i] representing the maximum number of copies available. We also have a knapsack with a maximum weight capacity capacity. For the item at index i, we can take anywhere from 0 up to counts[i] copies.