The knapsack problem is as follows. You are trying to move the maximum number of objects as possible, but your knapsack can only carry up to a maximum weight W. This means that each object is assigned a weight.
Now, to solve this problem we need to think a little differently than we traditionally think about the more basic problems in computer science. We're left with some fairly basic assumptions from an algorithm perspective
- An object can only be used once
- If the weight of an object being tested exceeds the current knapsack weight, it also cannot be used
- Order does not matter, because the objects can be used in any combination. This implies that with a brute force approach, there are n2-1, where n is equal to the total number of objects, possible combinations which can add up quite quickly with a large data set.
We can observe one additional item that can help us reduce the number of combinations. If we sort the data set before invoking the algorithm and we exceed the weight W as we sum up items to check, and we can assume that any item after that will also fail.
We will use the input list of {10, 40, 29, 4, 12, 45, 32, 34}, and W = 100 as an example for the remainder of this entry.
To begin with, we'll sort the array to {4, 10, 12, 29, 32, 34, 40, 45}. We should also note that n here is equal to 8. There are a few different ways to go about this, but one of the ideal ways is to use recursion. You can view this as a tree, or even a forest where each element in the list can act as the root node, and then traverse each path to act as the sum. This first step of thinking recursively is key in solving the problem.
For example, we'll start with 4. We'll use a depth first search method and continue along the path of the sorted list. 4 + 10 + 12 + 29 + 32 = 87. If we add 34, we get 121 which is over the weight limit of W, which in this case is equal to 100. In this example, we can also stop looking further down that side of the tree because any weight after 32 is also going to fail the test.
So we're at a point where it's not easy to visualize without an image, so I'll paste one below.
 |
| 34 is the last option we try in this path. Currently, it's just a linear tree |
Given this, we can see that the node of 32 gives us a maximum possible weight of 87 from this path. So we need to try other solutions. So we remove 32 from the solution, and try 34. This gives 4 + 10 + 12 + 29 + 34 = 89. Our maximum weight is now 89, and we're once again confronted with an issue where anything after 34 will fail our weight test.
So once again this pattern continues and we remove 34 from the solution and try 40. This gives 4 + 10 + 12 + 29 + 40 = 95. Now our maximum obtained weight is 95, which again makes the other solutions at this point in the algorithm incorrect. We also, once again, run into the issue of anything after 40 will fail the test, so we pop 40 off of the list and try 45.
For those paying attention, their intuition might have gone off on this part. If we add 45, we get 4 + 10 + 12 + 29 + 45 = 100 exactly. In our problem, there is no need to continue. So while this was an apparently short run, it's important to note that we made end up going through all possible combinations - the failed tests when it reaches > 100. However, the worst case is still n2 - 1 because we may have an input list that never exceeds the weight limit W. Below is a full tree of the attempts made with 4 as a starting point.
So you can see how it will begin to branch out. If we did not find 45 as a solution, we would then backtrack to 12 and start with a similar idea and begin adding each of the remaining numbers and stopping when the current weight > W.
Similarly, if, for the sake of argument, we did not find any solutions that began with 4, we would eventually pop back all values and start with 10 as the root node. This is called backtracking, and with the way the algorithm works that once something fails, we revert to an earlier state which lends itself well to recursion.
This solution however is only one way, and still runs the risk of a high number of operations and checks depending on the solution set. So we need to be a little more clever to reduce this. Recursion is also the entry way to thinking dynamically. With that, I mean there is a technique called dynamic programming. In a nutshell, dynamic programming uses stored data to prevent the recalculation of items in an algorithm. For example, if a certain maximum weight has already been calculated for a certain combination, then we can store that in an array and consult that instead of redoing the calculation. With recursion, this can make a particular difference as we'd be removing complete levels of the tree.
This is the way my group in my data structures class went about it. This not the only, or even the best solution. I'm leaving this entry intentionally brief in the description because while this is a "correct" solution, there is a more clever way to think recursively which is something I learned sometime later. In the next entry, I will go into more detail on a solution that more accurately paves the way to dynamic programming. As this solution stands, it becomes difficult to represent with a tabular approach.
Until next time!
Similarly, if, for the sake of argument, we did not find any solutions that began with 4, we would eventually pop back all values and start with 10 as the root node. This is called backtracking, and with the way the algorithm works that once something fails, we revert to an earlier state which lends itself well to recursion.
This solution however is only one way, and still runs the risk of a high number of operations and checks depending on the solution set. So we need to be a little more clever to reduce this. Recursion is also the entry way to thinking dynamically. With that, I mean there is a technique called dynamic programming. In a nutshell, dynamic programming uses stored data to prevent the recalculation of items in an algorithm. For example, if a certain maximum weight has already been calculated for a certain combination, then we can store that in an array and consult that instead of redoing the calculation. With recursion, this can make a particular difference as we'd be removing complete levels of the tree.
This is the way my group in my data structures class went about it. This not the only, or even the best solution. I'm leaving this entry intentionally brief in the description because while this is a "correct" solution, there is a more clever way to think recursively which is something I learned sometime later. In the next entry, I will go into more detail on a solution that more accurately paves the way to dynamic programming. As this solution stands, it becomes difficult to represent with a tabular approach.
Until next time!
