DAA - Kesirli Sırt Çantası

Açgözlü algoritma, Sırt Çantası problemi olarak adlandırılan iyi bilinen bir problemle çok iyi anlaşılabilir. Aynı problem diğer algoritmik yaklaşımlar kullanılarak çözülebilse de, Açgözlü yaklaşım Fraksiyonel Sırt Çantası problemini makul bir şekilde iyi bir zamanda çözer. Sırt çantası sorununu ayrıntılı olarak tartışalım.

Sırt Çantası Sorunu

Her biri bir ağırlık ve bir değere sahip bir öğe kümesi verildiğinde, toplam ağırlığın belirli bir sınırdan küçük veya ona eşit ve toplam değerin mümkün olduğunca büyük olması için bir koleksiyona dahil edilecek bir öğe alt kümesi belirleyin.

Sırt çantası problemi, kombinatoryal optimizasyon problemidir. Gerçek dünya problemlerinin birçok, daha karmaşık matematiksel modelinde bir alt problem olarak görünür. Zor problemlere genel bir yaklaşım, en kısıtlayıcı kısıtlamayı belirlemek, diğerlerini görmezden gelmek, bir sırt çantası problemini çözmek ve bir şekilde göz ardı edilen kısıtlamaları karşılamak için çözümü ayarlamaktır.

Başvurular

Çoğu durumda, bazı kısıtlamalarla birlikte kaynak tahsisi durumunda, sorun, Sırt Çantası problemine benzer bir şekilde türetilebilir. Aşağıda bir dizi örnek verilmiştir.

• Ham maddeleri kesmenin en az savurgan yolunu bulmak
• portföy optimizasyonu
• Stok sorunları kesme

Problem Senaryosu

Bir hırsız, bir mağazayı soyuyor ve maksimum ağırlık taşıyabilir. Wsırt çantasına. Mağazada mevcut n adet ürün var vei^th öğe w_i ve karı p_i. Hırsız hangi eşyaları almalı?

Bu bağlamda eşyalar, hırsızın maksimum kar elde edeceği eşyaları taşıyacak şekilde seçilmelidir. Dolayısıyla hırsızın amacı karı maksimize etmektir.

Ürünlerin niteliğine göre Sırt Çantası sorunları şu şekilde kategorize edilir:

• Kesirli Sırt Çantası
• Knapsack

Kesirli Sırt Çantası

Bu durumda, parçalar daha küçük parçalara bölünebilir, böylece hırsız, parçaların parçalarını seçebilir.

Sorun açıklamasına göre,

• Var n mağazadaki ürünler

• Bayrağın ağırlığı i^th öğe $ w_ {i}> 0 $

• Kar i^th öğe $ p_ {i}> 0 $ ve

• Sırt Çantasının kapasitesi W

Sırt Çantası probleminin bu versiyonunda, eşyalar daha küçük parçalara bölünebilir. Yani hırsız sadece bir kısmını alabilirx_i nın-nin i^th öğe.

$$ 0 \ leqslant x_ {i} \ leqslant 1 $$

i^th öğe sırt çantasındaki toplam ağırlığa $ x_ {i} .w_ {i} $ katkıda bulunur ve toplam kara $ x_ {i} .p_ {i} $ kar eder.

Dolayısıyla, bu algoritmanın amacı

$$ maximize \: \ displaystyle \ sum \ limits_ {n = 1} ^ n (x_ {i} .p _ {} i) $$

kısıtlamaya tabi,

$$ \ displaystyle \ sum \ limits_ {n = 1} ^ n (x_ {i} .w _ {} i) \ leqslant W $$

En uygun çözümün sırt çantasını tam olarak doldurması gerektiği açıktır, aksi takdirde kalan öğelerden birinin bir kısmını ekleyebilir ve toplam kârı artırabiliriz.

Böylece optimal bir çözüm şu şekilde elde edilebilir:

$$ \ displaystyle \ toplam \ limitler_ {n = 1} ^ n (x_ {i} .w _ {} i) = W $$

Bu bağlamda, önce bu öğeleri $ \ frac {p_ {i}} {w_ {i}} $ değerine göre sıralamalıyız, böylece $ \ frac {p_ {i} +1} {w_ {i } +1} $ ≤ $ \ frac {p_ {i}} {w_ {i}} $. Buraya,x öğelerin kesirlerini depolayan bir dizidir.

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if weight + w[i] ≤ W then  
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x

Analiz

Sağlanan öğeler zaten azalan bir $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $ sırasına dizilmişse, bu durumda yükleme işlemi bir süre alır O(n); Bu nedenle sıralama dahil toplam süreO(n logn).

Misal

Sırt çantasının kapasitesinin W = 60 ve sağlanan öğelerin listesi aşağıdaki tabloda gösterilmektedir -

Öğe	Bir	B	C	D
Kar	280	100	120	120
Ağırlık	40	10	20	24
Oran $ (\ frac {p_ {i}} {w_ {i}}) $	7	10	6	5

Sağlanan öğeler $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $ temelinde sıralanmadığı için. Sıralamanın ardından öğeler aşağıdaki tabloda gösterildiği gibidir.

Öğe	B	Bir	C	D
Kar	100	280	120	120
Ağırlık	10	40	20	24
Oran $ (\ frac {p_ {i}} {w_ {i}}) $	10	7	6	5

Çözüm

Tüm öğeleri $ \ frac {p_ {i}} {w_ {i}} $ 'ya göre sıraladıktan sonra. Öncelikle hepsiB ağırlığı olarak seçilir Bsırt çantasının kapasitesinden daha az. Sıradaki eşyaA Sırt çantasının mevcut kapasitesi, sırt çantasının ağırlığından daha büyük olduğu için seçilir. A. Şimdi,Csonraki öğe olarak seçilir. Bununla birlikte, sırt çantasının kalan kapasitesi, sırt çantasının ağırlığından daha az olduğu için tüm öğe seçilemez.C.

Bu nedenle, fraksiyonu C (yani (60 - 50) / 20) seçilir.

Artık Sırt Çantasının kapasitesi seçilen eşyalara eşit. Bu nedenle, başka öğe seçilemez.

Seçilen öğelerin toplam ağırlığı 10 + 40 + 20 * (10/20) = 60

Ve toplam kâr 100 + 280 + 120 * (10/20) = 380 + 60 = 440

En uygun çözüm budur. Herhangi bir farklı öğe kombinasyonunu seçerek daha fazla kar elde edemeyiz.