Understanding the 0/1 knapsack problem

In many applications, software must choose between several competing options while operating under limited resources such as time, memory, or computational capacity. 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 0/1 knapsack problem, where the "0/1" indicates that each item must be either included entirely or left out entirely; no partial items are allowed.

The 0/1 knapsack problem is a foundational problem in dynamic programming and appears frequently in applications such as portfolio optimization, resource allocation in computing systems, cargo loading, budget planning, and project selection.

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

The 0/1 knapsack problem

Consider we are given n 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. Each item can either be included in the knapsack or excluded; we cannot take a fraction of an item.