The 0/1 knapsack problem is a common problem that involves maximizing the value of items in a knapsack while ensuring that the total weight of the items doesn't exceed the knapsack's capacity.
Let's first use greedy algorithms to solve this problem. Suppose you’re a greedy thief. You’re in a store with a knapsack, and there are all these items you can steal. But you can only take what you can fit in your knapsack. The knapsack can hold 35 pounds.
You’re trying to maximize the value of the items you put in your knapsack. What algorithm do you use? Let us say we use the greedy strategy. It is pretty simple:
Pick the most expensive thing that will fit in your knapsack.
Pick the next most expensive thing that will fit in your knapsack. And so on.
Except this time, it doesn’t work! For example, suppose there are three items you can steal.
Your knapsack can hold 35 pounds of items. The stereo system is the most expensive, so you steal that. Now you don’t have space for anything else.
You got $3,000 worth of goods. But wait! If you’d picked the laptop and the guitar instead, you could have had $3,500 worth of loot!
The greedy strategy doesn’t give you the optimal solution here. But it gets you pretty close. Let's try it with another approach.
The simplest algorithm is this: you try every possible set of goods and find the set that gives you the most value.
This works, but it’s really slow. For 3 items, you have to calculate 8 possible sets. For 4 items, you have to calculate 16 sets. With every item you add, the number of sets you have to calculate doubles! This algorithm takes O(2ⁿ) time, which is very, very slow.
We can solve the Knapsack problem using Dynamic Programming. Dynamic programming starts by solving subproblems and builds up to solving the big problem. For the knapsack problem, you’ll start by solving the problem for smaller knapsacks (or “sub-knapsacks”) and then work up to solving the original problem.
Every dynamic programming algorithm starts with a grid. Here’s a grid for the knapsack problem.
The rows of the grid are the items, and the columns are knapsack weights from 1 lb to 4 lb. You need all of those columns because they will help you calculate the values of the sub-knapsacks. The grid starts out empty. You’re going to fill in each cell of the grid. Once the grid is filled in, you’ll have your answer to this problem!
Start with the first row. This is the guitar row, which means you’re trying to fit the guitar into the knapsack. At each cell, there’s a simple decision: do you steal the guitar or not? Remember, you’re trying to find the set of items to steal that will give you the most value. The first cell has a knapsack of capacity 1 lb. The guitar is also 1 lb, which means it fits into the knapsack! So the value of this cell is $1,500, and it contains a guitar.
Like this, each cell in the grid will contain a list of all the items that fit into the knapsack at that point. Let’s look at the next cell. Here you have a knapsack of capacity 2 lb. Well, the guitar will definitely fit in there!
The same for the rest of the cells in this row. Remember, this is the first row, so you have only the guitar to choose from. You’re pretending that the other two items aren’t available to steal right now.
At this point, you’re probably confused. Why are you doing this for knapsacks with a capacity of 1 lb, 2 lb, and so on, when the problem talks about a 4 lb knapsack? Remember how I told you that dynamic programming starts with a small problem and builds up to the big problem? You’re solving subproblems here that will help you to solve the big problem.
Remember, you’re trying to maximize the value of the knapsack. This row represents the current best guess for this max. So right now, according to this row, if you had a knapsack of capacity 4 lb, the max value you could put in there would be $1,500.
Let’s do the next row. This one is for the stereo. Now that you’re on the second row, you can steal the stereo or the guitar. At every row, you can steal the item at that row or the items in the rows above it. So you can’t choose to steal the laptop right now, but you can steal the stereo and/or the guitar. Let’s start with the first cell, a knapsack of capacity 1 lb. The current max value you can fit into a knapsack of 1 lb is $1,500.
Should you steal the stereo or not? You have a knapsack of capacity 1 lb. Will the stereo fit in there? Nope, it’s too heavy! Because you can’t fit the stereo, $1,500 remains the max guess for a 1 lb knapsack.
Same thing for the next two cells. These knapsacks have a capacity of 2 lb and 3 lb. The old max value for both was $1,500. The stereo still doesn’t fit, so your guesses remain unchanged. What if you have a knapsack of capacity 4 lb? Aha: the stereo finally fits! The old max value was $1,500, but if you put the stereo in there instead, the value is $3,000! Let’s take the stereo.
You just updated your estimate! If you have a 4 lb knapsack, you can fit at least $3,000 worth of goods in it. You can see from the grid that you’re incrementally updating your estimate.
Let’s do the same thing with the laptop! The laptop weighs 3 lb, so it won’t fit into a 1 lb or a 2 lb knapsack. The estimate for the first two cells stays at $1,500.
At 3 lb, the old estimate was $1,500. But you can choose the laptop instead, and that’s worth $2,000. So the new max estimate is $2,000!
At 4 lb, things get really interesting. This is an important part. The current estimate is $3,000. You can put the laptop in the knapsack, but it’s only worth $2,000.
Hmm, that’s not as good as the old estimate. But wait! The laptop weighs only 3 lb, so you have 1 lb free! You could put something in this 1 lb. What’s the maximum value you can fit into 1 lb of space? Well, you’ve been calculating it all along.
According to the last best estimate, you can fit the guitar into that 1 lb space, and that’s worth $1,500. So the real comparison is as follows.
You might have been wondering why you were calculating max values for smaller knapsacks. I hope now it makes sense! When you have space left over, you can use the answers to those subproblems to figure out what will fit in that space. It’s better to take the laptop + the guitar for $3,500.
The final grid looks like this.
There’s the answer: the maximum value that will fit in the knapsack is $3,500, made up of a guitar and a laptop!
Now, let's generalize this with a06. formula. Each cell’s value gets calculated with the same formula. Here it is.
You can use this formula with every cell in this grid, and you should end up with the same grid I did. Remember how I talked about solving subproblems? You combined the solutions to two subproblems to solve the bigger problem.
We finally figured out the Knapsack problems. But there are a few important things you need to keep in mind for the Knapsack problem.
We have studied Knapsack Problem and how to solve it. However, while solving the problem, keep the following things in mind.
It is possible that the best solution doesn’t fill the knapsack completely. Suppose you could also steal a diamond. This is a big diamond: it weighs 3.5 pounds. It’s worth a million dollars, way more than anything else. You should definitely steal it! But there’s half a pound of space left, and nothing will fit in that space.
Dynamic programming only works when each subproblem is discrete—when it doesn’t depend on other subproblems.
You cannot steal fractions of items. With the dynamic-programming solution, you either take the item or not. There’s no way for it to figure out that you should take half an item.
The order of rows of grid does not matter.
The value of column cannot go down in subsequent iterations.
This was it. Thankyou for reading.