0/1 Knapsack Explainer with Graphs and DP Table

I really enjoyed tackling the 'ol 0/1 knapsack problem but had to do a lot of background research in order to get it. I binged watched MIT’s Open Course ware on YouTube heavily. Erik Demaine is a real life Sheldon Cooper and often themes his shirt to match the topic. Well worth the watch. This is what I was able to figure out after watching 8 hrs so you don’t have to.

Here’s what Codecademy was trying to show us with the DP Table:

DPTABLE

Now what wasn’t precisely explained is how to then figure through what items would be selected. Though this wasn’t explained in MIT’s videos. Look up good ol’ William Fiset for that.
What you want to do is look at the bottom right hand corner:

k5

So as you can see: If we look the poor old necklace never got picked. 550 is in the bottom right hand corner. We see the value above is the same. A change in value means the item got picked. so then that means Earrings got picked. They weigh 3lbs. So now 5-3 means we look at the knapsack of capacity 2.

k2

We see the change in value to 250-0 so that means the one ring to rule them all (the only ring worth the thievery) was chosen.

Now what I learnt from the lectures comes into play around about now. Everything in the DP table is a subproblem. So if you only had a backpack that could 1 or 2 or 3 what subset out of the given items would you choose for the MAX value I can get using a certain weight?

so lets assign Items to I
knapsacks to J

We also know that there are only two choices you’re making for any item. Do I take it or not?
So your either keeping capacity or making money.

DP of [i][j] = max(dp [i+1][j] (not taking the item)
vi(value of the item) [i+1][j-Weight Capacity]

The thing is you need to people to express this relationship in order to solve the problem. It will be no good just understanding that oh yes this is a dp table issue and plodding along from there.

What I found exceptionally useful is that you can also view any DP problem graphically. And basically consider every DP problem as a shortest path in a DAG:

Graph

So whats great about this is a lot less simple math error prone.

And to be clear the done column can be ommitted and you can connect the source node to each one of the different weight capacities and have them end at a single destination node. the weight of the edge in any of these cases is 0.

A node stores a state of the object and a weight. The edges are the value of the item.

The graph solution only has you care about one layer. One object at a time, So if you want to use my table:

We start at the source node and we connect to node 1 with 0 weight. this connects to item 2 with 0 weight all the way to the done and end node which as I type this I realize I forgot to add that arrow but its 0.

Now let say you pick the ring. the edge then because the earrings weigh 1 lbs you now find yourself at object 2 weight 1 (2,1) you can choose not to include other objects (3,1) (4,1) all with an edge cost of zero and exit. This is of course a viable option for any timid thief. But that’s not what we’re all here for.

OR… continue the heist with the earrings and find yourself at object 3 , edge weight 300, with only one lb of Capacity left at (3,4) . Since we do not have a bag with capacity 9 we exit with the 550$.

OR you could have not bothered with all the other two objects and held out for the Necklace and found yourself at (4,5) with 500$.

Then if you stick to what Codecademy taught you you would run DFS with topsort but that’s 0(v+e).

You’re better off teaching yourself Bellman Ford … flipping the edgeweights to negative values and then you’re looking at a sweet 0(V*E) run time.

As for space optimizations… The DP Table all you have to do is store the last column for the max value.

Hope this helps.

3 Likes

Erik Demaine is a rockstar for sure!

My take is that with these things it really does depend on how deeply one wants to dig at these topics. Algorithms/data structures are tools. Some people are going to just need a tool that gets the job done well enough and others are going to craft/analyze the toolset itself (and of course, there’s a subset of people that want to do both things).

That being said I prefer the more theoretical side myself. So very nice post!

1 Like

Aw shucks. Thanks Pita :wink: that means a lot Yeah I need to know how and why it works. I have way too many: BUT WHY THO’s? . Back to SWE is also a good resource for anyone feeling demoralized. He makes you feel like you can solve all the things. Oh my gosh. My love for Erik Demaine knows no bounds. He is amazing. I’ve gotten so off track looking into his origami adventures and his Nova special. Gosh I wish I had his mighty mighty brain of accomplishment.

Thanks for posting this! Wow, what a problem… It took a few hours and a couple of cups of coffee to get to an okay level of understanding the problem. This topic just begs for some extra instruction outside of the instructions and pseudo-code presented. I enjoyed a little bit of Erik Demaine but also found this other guy (Abdul Bari). He explains this stuff in a very understandable and a bit less theoretical way. I found it really helpful to fill out the problem in a grid on a sheet of paper while watching his youtube presentation. This made it a bit easier to turn it into JS code. Here are the links:

Abdul Bari - 0/1 Knapsack Problem - 2 methods

Abdul Bari - 0/1 Knapsack Problem - whiteboard coding solution

1 Like

Ah yes. Caffeine the brain brute force solution :partying_face:. Definitely seen some of his videos before and I didn’t take note of who he was. Thanks for re-introducing me !! Totally agree that some of the problems especially the rain water one which I still think about from time to time in all honesty… . And Erasthothenes (sp?!) I never seen that before because I did not have rad math teachers apparently. All of these just make we want to deep dive. William Fiset actually has a whole series of neat coding questions like that. The first one I ever watched was the magic cows. That got me so hooked.

1 Like