Grokking the Coding Interview: The Original Course
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!
yash patel

yash patel

· 9 days ago

I think you can also include dedicate problems to unbounded knapsack as well. It is not there.

Reading Progress

0%

Vote for new content