What is the Knapsack Problem?

The Knapsack Problem is a famous Dynamic Programming Problem that falls in the optimization category.

It derives its name from a scenario where, given a set of items with specific weights and assigned values, the goal is to maximize the value in a knapsack while remaining within the weight constraint.

Each item can only be selected once, as we don’t have multiple quantities of any item.

In the below example, the weights of different honeycombs and the values associated with them are provided. The goal is to maximize the value of honey that can be fit in the bear’s knapsack.

Example

Let’s take the example of Mary, who wants to carry some fruits in her knapsack and maximize the profit she makes. She should pick them such that she minimizes weight ( $<= bag's$ $capacity$) and maximizes value.

Here are the weights and profits associated with the different fruits:

Items: { Apple, Orange, Banana, Melon }

Weights: { 2, 3, 1, 4 }

Profits: { 4, 5, 3, 7 }

Knapsack Capacity: 5

Fruits Picked by Mary:

Banana + Melon

💰Profit = 10

Banana and Melon is the best combination, as it gives us the maximum profit (10) and the total weight does not exceed the knapsack’s capacity (5).

Basic Solution

The problem can be tackled using various approaches: brute force, top-down with memoization and bottom-up are all potentially viable approaches to take.

The latter two approaches (top-down with memoization and bottom-up) make use of Dynamic Programming. In more complex situations, these would likely be the much more efficient approaches to use.