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 xdimensional. 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
twentyfive. We pack an item value v_{1} of size ten into the sack.
Then we pack another item of value v_{2} 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_{3}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_{4} 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 oftenmisunderstood
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);
}
