Greedy Algorithm



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

Lemma 5.2. Let q 1 > q 2 . Then in any optimal solution, either s 1 = 1 or s 2 = 0 .


Proof. A proof by contradiction. Assume an optimal solution exists with s 1 < 1 and s 2 > 0.
1 This is the relaxation of the indicator vector we formulated the Knapsack problem around. In Knapsack, we restrict s i { 0 , 1 } .

Then for some small d > 0, we can define a new fractional subset by




s j 1 = s 1 + d / w 1 , s j 2
= s 2 - d / w 2 (5.1)

This will still be a fractional subset and still satisfy the capacity constraint and will increase the value by



v 1 d


w 1
v 2 d
- w 2
= d ( q 1 - q 2 ) > 0 (5.2)

This contradictions the assumed optimality. Therefore either s 1 = 1 or s 2 = 0.

This tells us that if we sort the items by quality, we can greedily pick the items by best to worst quality.


Algorithm 5.3 (Fractional Knapsack) . Sort the items by quality so that v 1 / w 1. . . v n / w n . Initialize C = 0 (to represent the weight of items already in the knapsack). For each i = 1 to n , if w i < W - C , pick up all of item i . If not, pick up the fraction ( W - C ) / w i and halt.


Proof of Correctness. By the lemma above, we should pick up entire items of the highest quality until no longer possible. Then we should pick the maximal fraction of the item of next highest quality and the lemma directly forces all other items to not be picked at all.


Complexity. We need to only sort the values by quality and then in linear time select the items. Suppose the item values and weights are k bits integers for k = O (log n ). We need to compute ea c h q i to sufficie n t accuracy; s p ecificall y , if q i - q j > 0 then
v i w j - v j w i 1
q - q = > ≥ 2 - 2k (5.3)

i j w i w j
w i w j



Therefore, w e only need O ( k ) bits of accurac y . This can b e computed in O ˜ ( k ) time p er q i and therefore total n O ˜ (log n ). The total sorting time for p er-comparison cost of k is O ( nk log n ). This brings the total complexity to O ( n log 2 n ).

A final note about the fractional knapsack relaxation. By relaxing the constraint to allow fractional components of items, any optimal solution to fractional knapsack ≥ solution to classical knapsack. Also, our solution is almost integer; only the last item chosen is fractional.






    1. 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 ©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