Greedy Algorithm



Download 97,97 Kb.
bet1/12
Sana23.06.2022
Hajmi97,97 Kb.
#696905
  1   2   3   4   5   6   7   8   9   ...   12
Bog'liq
greedy (1)





  1. Greedy Algorithm

The second algorithmic strategy we are going to consider is greedy algorithms. In lay- man's terms, the greedy method is a simple technique: build up the solution piece by piece, picking whatever piece looks best at the time. This is not meant to be precise, and sometimes, it can take some cleverness to figure out what the greedy algorithm really is. But more often, the tricky part of using the greedy strategy is understanding whether it works! (Typically, it doesn't.)
For example, when you are faced with an NP-hard problem, you shouldn't hope to find an efficient exact algorithm, but you can hope for an approximation algorithm. Often, a simple greedy strategy yields a decent approximation algorithm.
    1. Fractional Knapsack


Let’s consider a relaxation of the Knapsack problem we introduced earlier. A relaxation of a problem is when we simplify the constraints of a problem in order to make the problem easier. Often we consider a relaxation because it produces an approximation of the solution to the original problem.

Σ Σ
Exercise 5.1 (Fractional Knapsack) . Like the Knapsack problem, there are n items with weights w 1 ,. . . , w n and values v 1 ,. . . , v n with a Knapsack capacity of W. However, we are allowed to select a fraction of an item. The output should be a fractional subset s of the items maximizing v ( s ) = i s i v i subject to the capacity constraint s i w iW. _ By a fractional subset, we mean a vector s = ( s 1 , . . . , s n ) with all 0 ≤ s i ≤ 1. 1
T o sol v e this problem, let's i n tr o duce the notion of quality of an item: q i = v i / w i . I n tu- itively , if the item was say a block of gold, it would be the dollar value of a single kg of the gold. The greedy strategy we are going to employ is going to picking items from highest to lowest quality. But first a lemma:

Download 97,97 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6   7   8   9   ...   12




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©www.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