Algorithms and Data Structures
Quick Links
What's New
Home
Contacts
Course Book
Java Book
JDK & JDSL
Slides
Notes
Demos
Exercises
Marks
 
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 <= 9
We 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
I could take object A, or not take object A. Assume I take object A, I could then take object B as well, or decide not to take object B. Assume I decide not to take object B. I could then decide to take object C or decide not to take object C ... and so on. I have a sequence of decisions, taking (1) or not taking (0) an object. In total, with the above 5 objects, I will have 2 to the power 5 possibilities, and each of these can be represented as a sequence of 1' and 0's.

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
We grow a tree, where in the left branch we decide to take an object, and the right branch we decide not to take an object. At depth i in the tree we will have considered i objects. When at a node in the tree, if the weight of the current combination exceeds the weight constraint we can stop exploring that branch (ie. we prune out that part of the search tree). We maintain a global variable for the best solution found so far, and the value of the best solution found so far. During exploration, if the current combination is valid (ie. its combined weight is less than or equal to the weight constraint) and its value is the best found so far, we record it (for prosperity:).

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 CS
The 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
There are 2 obvious improvements. The first is to sort the vectors such that we consider objects in decreasing order of value over weight ie. consider the object first that has most value per unit of weight. We can then exploit this such that when ever we can determine at step 2 that the current solution cannot be extended to a solution that is better than the best so far, we can suppress the recursive calls at steps 3 and 4. That is, we could look at the sum of the values of the remaining objects. If we add those to CV and this is less than or equal to BV we can return. We can do better estimates, but the cost goes up in doing this. However the better estimate should lead to a more efficient pruning of the search space, and this may be economical. 

Java source code  for (simple solutions to)  Knapsack.java  and Test.java


Copyright © Patrick Prosser 1999.