Source code online books for professionals by professionals



Download 4,67 Mb.
Pdf ko'rish
bet117/266
Sana31.12.2021
Hajmi4,67 Mb.
#213682
1   ...   113   114   115   116   117   118   119   120   ...   266
Bog'liq
2 5296731884800181221

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 unconsciousthat’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 

Download 4,67 Mb.

Do'stlaringiz bilan baham:
1   ...   113   114   115   116   117   118   119   120   ...   266




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish