Algorithms and Data Structures | |||||
|
0-1
Knapsack Problem
In the knapsack problem we are given a set of objects where each object has a weight and a value. We are given a container of a given capacity, imposing a weight constraint. The problem is then to place as many objects as possible into the container such that the weight constraint is not violated, and the sum of the values of the objects in the container is a maximum. Below is an example A B C D E Weights 3 8 6 4 2 Values 2 12 9 3 5 Capacity <= 9We have 5 objects, A, B, C, D, E, with weights (respectively) 3 8 6 4 2 and values (respectively) 2 12 9 3 5. We must select objects such that their combined weights are less than or equal to 9, and the value of the objects selected is a maximum. There are many real world instances of this problem. One example comes from the financial world, where the objects corresponds to blocks of shares or bonds, and have a corresponding cost (weight) and return on investment (value), and the capacity constraint corresponds to the amount of capital to be invested. We then wish to invest such that our return is maximised. A crude solution
For example (0 1 0 1 0) would correspond to take B and take D. We could generate all 2 to the power 5 possibilities, evaluate each, discarding those that violate the capacity constraint, and comparing the legal combinations. We then select the valid combination of maximum value. A better way
The above description corresponds to the 0-1-knapsack and can be described as follows 0-1-knapsack Assume we have the vectors Weight and Value such that Weight[i] is the weight of the ith object and Value[i] is the value of the ith object, a global variable BS for best solution, and BV for best value (initialised to -999), n being the number of objects, and Capacity being the capacity constraint. The parameters to the function are as follows: i is the depth in the search tree, and we consider selecting, initially 1 CS is the current solution, a list of objects to take and is initially the empty set. CW is the weight of the current solution, initially zero CV is the value of the current solution, initially zero 0-1-knapsack i CW CV CS 1. if the current solution is invalid (ie. CW > Capacity) or we have explored all options (ie i > n) then do nothing (ie. return) 2. At this point the current solution is valid, and there are objects to consider. Determine if the current solution is best that we have encountered so far. if current value is greater than the best value (ie. CV > BV) then save as best (ie. BV becomes CV, and best solution BS becomes the current solution CS). 3. Consider extending the search such that we select the next object 0-1-knapsack (i+1) (CW + Weight[i]) (CV + Value[i]) (push i onto CS) 4. Consider extending the search such that we do not select the next object 0-1-knapsack (i+1) CW CV CSThe above function explores all possibilities, and at step 1 determines if the current partial solution can be extended. If it cannot then the search is pruned. If it can be extended we then determine if we have found a new best solution (step 2), and then branch out by selecting the ith item and proceeding (step 3) then not selecting the ith item and proceeding (step 3). Improvements
Java source code for (simple solutions to) Knapsack.java and Test.java |