Interview Question: 0-1 Knapsack

In this video, I show several ways to approach the 0-1 knapsack problem.

Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We've helped thousands of students improve their interviewing and we can help you too.

You can also find me on

[rajastylez]

Dude you're amazing! I really appreciate that you began with the naive but intuitive recursive solution step-by-step!

[sujitamin]

Sam dude you are brillant in explaining algorithm

[alexeystaroverov]

please choose random values ( weights in this case) your 1, 2, 3 is nebulous and easy to confuse with indices

[keerthiluvmyguitar]

At the beginning, for the example you took up, you said that the max value is 220 while it actually is 280 since you can take one 20 and three 10 weighted objects.

[ridhwaans]

at 11:27 why didnt you put the return in an else clause. does it not make a difference?

[jsk]

Hi Sam, at 16:30, aren't you supposed to have one more column of "6"? Given the way problem is worded, you can choose to select all the items in the given array as long as "max weight" input parameter is greater than the total weight of all the items in the list. As a result, you should have included column for total weight of "6" where all the items are selected for the knapsack where the "max weight" is greater than 6. Right?

[shenth]

I'm not getting this part - Math.max(cache[i-1][j], cache[i-1][j-weights[i-1]] + vals[i-1]); - why adding the previous indexed value(i-1) of vals? you need to check if adding the current value (i) maximises the total value right

[KishanKumar-mzxr]

Please elaborate the point at 26:50. I couldn't get it.

[Han-veuh]

1. Why in nested loop, the asymmetry of i starting from 1 but j start from 0. I thought j can start from 1 too.
2. Is it coincidence that the value to weight ratios given are already in high to low order? I''m wondering how would changed ratio order affect both topdown/bottomup approaches?
3. Any examples of DP where we can practice cacheing for 3D? (this video is 2D, and i find the linking from current problem to subproblems most difficult)
4. The off-by-1 representation of input vs cache makes it easy to make mistakes, is this a characteristic of most bottom up solutions? Are there example problems where off-by-2 is needed, or where multiple different cache representations can be used for the same DP problem? (something like multiple array representations of binary trees)

Extra notes to readers who may have same questions as me:
Q1: Why doesn't [j-weights[i-1]] go out of bounds to the left?
A1: Because the inner loop keeps moving j rightwards until there's enough weight such that even after minus, the index will definitely not exceed left bound
Q2: Why in the "we have enough weight to add current item" else path, there's a look back up 1 row (instead of staying at current row) in addition to moving left along columns.
A2: Moving left means "Assuming we use item represented by current row, what weight is left to be allocated to other items. Moving up is a must because each item can only be used once. After moving left, we acknowledge that current row's item is used up, so in the sub-problem the current state is looking back to, it cannot allow use of current row's item, so must jump back up 1 row.

[wattsmith]

That made the most sense of any DP video I've seen.

[dipenpatel]

I didn't get it the first time around, but with the code how you were traversing the 2d array made a lot more sense. Thanks for the great video

[piyush]

Great explanation. You can further decrease your space complexity by using only 1D array of weights since you are just checking the last row every time.

[RaymondLo]

Wish you can continue doing these kinda of videos. I like this format better than you writing with a whiteboard as it's kinda hard to read as well.

Either way, these interview exams are pretty ok if you study lots, but also takes up lots of your own time.

[soleypas]

I had problem understanding this problem years ago, thanks to you now I understood it :)

[erichlf]

Does java initialize an array to zero automatically?

[dev-skills]

can we ignore first row and first col of the matrix (as its always going to be containing zeros) ?

[garwar]

why i <= weights.length? Has to be i <= (weights.length - 1). No?

[pratomoardianto]

I'm sorry, I'm still confused! X(

[Samalot]

Thanks for this! Really appreciate it.

[AmmarRai]

How is it decided that a 6 x 4 array will be created? What determined those numbers?