# Knapsack

MediumLet's say you sell jewelry. Each item in your store has a specific

*weight*and*value*.You are asked to sell a bag that can hold a specific amount of weight.

Write a function that returns the

**maximum total value**that the bag can hold.For example, let's say you have a bag with a capacity of

*50 oz*, with the following items in stock:Index | Item | Weight | Value |
---|---|---|---|

0 | Ring | 15 oz | $2 |

1 | Necklace | 30 oz | $7 |

2 | Bracelet | 25 oz | $3 |

3 | Earrings | 20 oz | $12 |

These items are passed into your function as two array inputs, along with the bag capacity. Each item is represented by the same index in both arrays.

Note that you can only pick either 0 or 1 of each item, not a fraction of one nor a multiple.

### Examples

jewelry_values = [2, 7, 3, 12]jewelry_weights = [15, 30, 25, 20]capacity = 50output = knapsack(jewelry_values, jewelry_weights, capacity)print(output) # 19

Your function should return

`19`

, the sum of the value of a Necklace ($7) and earrings ($2) (Item 1 and Item 3), which fit in a *50 oz*bag.## Solution

## 8 Essential Recursion & Dynamic Programming Coding Interview Problems

Master Recursion & Dynamic Programming by trying the coding challenges below.

- 1.FibonacciEasy
- 2.Unique pathsMedium
- 3.KnapsackMedium
- 4.Subset sumMedium
- 5.Power setMedium
- 6.Coin changeMedium
- 7.Word breakHard
- 8.Longest common subsequenceHard