Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Introduction to 0/1 Knapsack Pattern

You are a thief with a bag that holds 8 units of weight. Each item can be taken once or left behind. Take the most valuable load you can carry.

item      A    B    C    D
weight    2    3    4    5
value     4    5    6   10        the best load is B + D, worth 15

Greedy fails here, and it is worth seeing why. Take the best value per unit of weight and you take A first, then D, filling 7 units for 14. Take the highest value first and you take D, then B, for 15. Neither rule is safe, because a choice that looks good now can use up room that a better item needed.

.....

.....

.....

Like the course? Get enrolled and start learning!