Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Introduction to 0/1 Knapsack Pattern

You have a bag with capacity 8. Each item has a weight and value. Choose the most valuable group that fits.

item      A   B   C   D
weight    2   3   4   5
value     4   5   6  10

best choice: B + D, value = 15

Each item can be taken once or skipped.

A greedy rule is not always correct. Choosing the best value-to-weight ratio may use space needed by a better combination.

We must compare both choices for every item:

  1. Skip the item.
  2. Take the item when it fits.

The answer also depends on the remaining capacity

.....

.....

.....

Like the course? Get enrolled and start learning!

Reading Progress

0%

Vote for new content