Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

0/1 Knapsack (medium)

Introduction

Given two integer arrays to represent weights and profits of ‘N’ items, find a subset of these items that will give us maximum profit such that their cumulative weight is not more than a given number ‘C’, and return the maxium profit. Each item can only be selected once, which means either we put an item in the knapsack or we skip it.

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 }

.....

.....

.....

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