Search

         
0.8.4 Knapsack Problem

The knapsack problem deals with packing known size objects into a space such that the value of these items is maximized. The objects and the space can be x-dimensional. The number of objects is unlimited but there are n classes of objects. All members of one class are the same size. All classes are different sizes.

In most versions of the knapsack problem the value of the classes is variable and we must maximize the value of the objects in the space.

Packing n types of objects into a fixed space s can be solved by a recursive algorithm.

int knap(int cap) 
{
  int i, space, max, t;

  /* N is the number of item classes */
  for (i = 0, max = 0; i < N; i++) 
  { 

    /* 
     * ... figure out how much space would be left if we packed this
     * class of item (current free space minus this item requirement)
     */
    space = cap - items[i].size;

    /* if the space is still positive (i.e. we can pack it legally)... */
    if (space >= 0)
    {

      /* ... then do it and recurse on the new (less) amount of free space */
      t = knap(space) + items[i].val;

      if (t > max) 
      {
        max = t;
      }
    }
  }

  /*
   * if we did not pack anything (i.e. nothing will fit) max = 0 and
   * return zero.  Else max is the ``most valuable'' way we can pack
   * at this point and we return its value to the previous layer.  If
   * the USING_ITEM_VALUES macro is not defined, all items are worth
   * one and we are trying to maximize the number of items we can fit,
   * not the value of items we can fit.
   */
  return(max);
}

The problem is that this solution is inefficient. Tracing the execution of the recursive solution you will notice that much of the algorithms time is spent recomputing the answer to a subproblem that it has seen in the past. For instance, if we have already discovered the best way to pack a space of size 14 once, why should we go though the process of computing it all over again? Yet the above solution does just that. Imagine we have a starting knapsack size of twenty-five. We pack an item value v₁ of size ten into the sack. Then we pack another item of value v₂ and size one into the sack. We now have fourteen free space in the knapsack and want to maximize the value we can fit into this space. Assume we do so.

Now we recurse out to the first instance of knap in the call stack and proceed to change the first item. We now pack an item of value v₃and size six as the first thing in the sack. In the following call to knap's loop, at some point, we pack a second item into the sack with a value of v₄ and a size of five. We now are facing the same exact problem we solved before: how to pack a free space of size fourteen and maximize the value. Because we have solved this problem, it would make sense to simply reuse the solution and avoid the recomputation. The recursive solution to the knapsack problem does not do this, though; rather it dumbly recomputes. In fact, because of the massive amounts of recumputation involved, an analysis of this recursive solution will discover that it takes exponential time. This is unacceptable for anything but the smallest problems.

Enter dynamic programming. This is an often-misunderstood concept; all it means is that if you have one large problem made up of many subproblems, the first time you tackle a subproblem save its result so that if you must handle the same subproblem again at some point you can skip the computation and just use the old result. Here's how we can use this technique to make the recursive example previously shown linear in complexity:

int knap(int cap) {
  int i, space, max, maxi, t;

  /* the first thing we do is see if we have an answer to how to pack
   * items into cap space maximizing the value of the items.  If so we
   * do not need to do anything but return!
   */

  if (max_known[cap] != UNKNOWN) 
  {
    return(max_known[M]);
  }

  /* if we got here we have not yet solved this problem, so lets do
   * it!
   */
  for (i = 0, max = 0; i < N; i++) 
  {

    /* see comments on recursive solution -- understand it before you
     * read this 
     */

    space = cap - items[i].size;
    if (space >= 0) 
    {
      t = knap(space) + items[i].val;
      if (t > max) 
      {
        max = t;
        maxi = i;
      }
    }
  }

  /* now that we have packed the required space as well as we can,
   * remember how well we could do it.  Thus, if we are ever required to
   * do it again we can just use this saved value...
   */

  max_known[cap] = max;
  item_known[cap] = items[maxi];

  return(max);
}