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.


The Value in the Bear's Knapsack can be maximized by adding the Honey Comb **2 & 3** to it!

**Total Weight = 150 gms + 350 gms
             = 500 gms**
             
**Total Value = 150 gms + 450 gms
             = 600 gms**


# 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:** 

> ## <center>Banana + Melon</center> 
> ## <center>💰Profit = 10</center> 

**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.

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. 