|
All the Girls. You know that I’ll never leave you. Not as long as she’s with someone. (
http://xkcd.com/770
)
Chapter 7
■
Greed Is Good? prove It!
143
The Knapsack Problem
This problem is, in a way, a generalization of the change-making problem, discussed earlier. In that problem, we used
the coin denominations to determine whether a partial/full solution was valid (don’t give too much/give the exact
amount), and the number of coins measured the quality of the eventual solution. The knapsack problem is framed
in different terms: We have a set of items that we want to take with us, each with a certain weight and value; however,
our knapsack has a maximum capacity (an upper bound on the total weight), and we want to maximize the total
value we get.
The knapsack problem covers many applications. Whenever you are to select a valuable set of objects (memory
blocks, text fragments, projects, people), where each object has an individual value (possibly be linked to money,
probability, recency, competence, relevance, or user preferences), but you are constrained by some resource (be it
time, memory, screen real-estate, weight, volume or something else entirely), you may very well be solving a version
of the knapsack problem. There are also special cases and closely related problems, such as the subset sum problem,
discussed in Chapter 11, and the problem of making change, as discussed earlier. This wide applicability is also its
weakness—what makes it such a hard problem to solve. As a rule, the more expressive a problem is, the harder it is to
find an efficient algorithm for it. Luckily, there are special cases that we can solve in various ways, as you’ll see in the
following sections.
Fractional Knapsack
This is the simplest of the knapsack problems. Here we’re not required to include or exclude entire objects; we might
be stuffing our backpack with tofu, whiskey, and gold dust, for example (making for a somewhat odd picnic). We
needn’t allow arbitrary fractions, though. We could, for example, use a resolution of grams or ounces. (We could be
even more flexible; see Exercise 7-6.) How would you approach this problem?
The important thing here is to find the value-to-weight ratio. For example, most people would agree that gold dust
has the most value per gram (though it might depend on what you’d use it for); let’s say the whiskey falls between the
two (although I’m sure there are those who’d dispute that). In that case, to get the most out of our backpack, we’d stuff
it full with gold dust—or at least with the gold dust we have. If we run out, we start adding the whiskey. If there’s still
room left over when we’re out of whiskey, we top it all off with tofu (and start dreading the unpacking of this mess).
This is a prime example of a greedy algorithm. We go straight for the good (or, at least, expensive) stuff. If we use
a discrete weight measure, this can, perhaps, be even easier to see; that is, we don’t need to worry about ratios. We
basically have a set of individual grams of gold dust, whiskey, and tofu, and we sort them according to their value.
Then, we (conceptually) pack the grams one by one.
Integer Knapsack
Let’s say we abandon the fractions, and now need to include entire objects—a situation more likely to occur in real
life, whether you’re programming or packing your bag. Then the problem is suddenly a lot harder to solve. For now,
let’s say we’re still dealing with categories of objects, so we can add an integer amount (that is, number of objects)
from each category. Each category then has a fixed weight and value that holds for all objects. For example, all gold
bars weigh the same and have the same value; the same holds for bottles of whiskey (we stick to a single brand) and
packages of tofu. Now, what do we do?
There are two important cases of the integer knapsack problem—the bounded and unbounded cases. The
bounded case assumes we have a fixed number of objects in each category,
4
and the unbounded case lets us use
as many as we want. Sadly, greed won’t work in either case. In fact, these are both unsolved problems, in the sense
that no polynomial algorithms are known to solve them in general. There is hope, however. As you’ll see in the next
chapter, we can use dynamic programming to solve the problems in pseudopolynomial time, which may be good
4
If we view each object individually, this is often called 0-1 knapsack because we can take 0 or 1 of each object.
Chapter 7
■
Greed Is Good? prove It!
144
enough in many important cases. Also, for the unbounded case, it turns out that the greedy approach ain’t half bad! Or,
rather, it’s at least half good, meaning we’ll never get less than half the optimum value. And with a slight modification,
you can get as good results for the bounded version, too. This concept of greedy approximation is discussed in more
detail in Chapter 11.
Note
■
this is mainly an initial “taste” of the knapsack problem. I’ll deal more thoroughly with a solution to the integer
knapsack problem in Chapter 8.
Huffman’s Algorithm
Huffman’s algorithm is another one of the classics of greed. Let’s say you’re working with some emergency central
where people call for help. You’re trying to put together some simple yes/no questions that can be posed in order to
help the callers diagnose an acute medical problem and decide on the appropriate course of action. You have a list of
the conditions that should be covered, along with a set of diagnostic criteria, severity, and frequency of occurrence.
Your first thought is to build a balanced binary tree, constructing a question in each node that will split the list (or
sublist) of possible conditions in half. This seems too simplistic, though; the list is long and includes many noncritical
conditions. Somehow, you need to take severity and frequency of occurrence into account.
It’s usually a good idea to simplify any problem at first, so you decide to focus on frequency. You realize that the
balanced binary tree is based on the assumption of uniform probability—dividing the list in half won’t do if some
items are more probable. If, for example, there’s an even chance that the patient is unconscious, that’s the thing to ask
about—even if “Does the patient have a rash?” might actually split the list in the middle. In other words, you want a
Do'stlaringiz bilan baham: |
