Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: 0/1 Knapsack

Introduction

Given the weights and profits of ‘N’ items, we are asked to put these items in a knapsack with a capacity ‘C.’ The goal is to get the maximum profit out of the knapsack items. Each item can only be selected once, as we don’t have multiple quantities of any item.

Let’s take Merry’s example, who wants to carry some fruits in the knapsack to get maximum profit. Here are the weights and profits of the fruits:

Items: { Apple, Orange, Banana, Melon }

Weights: { 2, 3, 1, 4 }

Profits: { 4, 5, 3, 7 }

Knapsack capacity: 5

.....

.....

.....

Like the course? Get enrolled and start learning!
D

DarkStar

· 4 years ago

There is a bug in the diagram/algorithm in the section "How can we find the selected items?"

When you realize dp[i][c] != d[i-i][c] and you decide to include the current index in the final path, you actually have to go up a row - NOT stay in the same row.

For example, assume that the capacity is 6 instead of 7. You start at 17 in row D. You see the same as the row above, so you go to row C. Since that 17 is not the same as the row above, you take it.

Solution so far: C

Then subtract the weight of the current row (3) and that takes you to weight 10 on the same row. That's not the same as the row above...so you include C again?

What you have to do is subtract the weight and go to the row above (in this case row B)

K

k

· 3 years ago

def solve_knapsack(self, profits, weights, capacity):
    n = len(profits)
    dp = [0] * (capacity + 1)
    for i in range(n):
        for j in range(capacity, weights[i] - 1, -1):
            dp[j] = max(profits[i] + dp[j - weights[i]], dp[j])
    return dp[capacity]
    return -1
L

Lit Martian

· 4 years ago

There is a mistake in the image of Bottom-up Dynamic Programming section where it should be 23 instead of 22 in the matrix for capacity/index

Show 1 reply
A

agustin.vaca

· 3 years ago

I understand we need to store values for when capacity = original capacity, but we're not storing anything for capacity = 0. Why not allocate [1,capacity] for the dp array?

C

Chris Malone

· 3 years ago

The question is poorly worded. It makes it seem like you are asking for the best subset when actually you are asking for the best score.

L

lejafilip

· 2 years ago

Ofc we propably won't get 1DP problem at interview in 2024+ but it is the best to start from the beginning.

Show 1 reply