Knapsack

Medium

Let'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 = 50

output = 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.

def knapsack(values: list[int], weights: list[int], capacity: int) -> int:
    # implement knapsack here
    return 0

1def knapsack(values: list[int], weights: list[int], capacity: int) -> int:
2    # implement knapsack here
3    return 0
4

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

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.