DAA - Knapsack Pecahan

Algoritma Greedy dapat dipahami dengan sangat baik dengan masalah yang terkenal disebut sebagai masalah Knapsack. Meskipun masalah yang sama dapat dipecahkan dengan menggunakan pendekatan algoritmik lainnya, pendekatan Greedy memecahkan masalah Fractional Knapsack secara wajar dalam waktu yang tepat. Mari kita bahas masalah Knapsack secara detail.

Masalah Knapsack

Dengan mempertimbangkan satu set item, masing-masing dengan bobot dan nilai, tentukan subset item untuk dimasukkan ke dalam koleksi sehingga bobot totalnya kurang dari atau sama dengan batas yang diberikan dan nilai totalnya menjadi sebesar mungkin.

Masalah knapsack terletak pada masalah optimasi kombinatorial. Ini muncul sebagai subproblem dalam banyak model matematika yang lebih kompleks dari masalah dunia nyata. Salah satu pendekatan umum untuk masalah sulit adalah dengan mengidentifikasi kendala yang paling membatasi, mengabaikan yang lain, memecahkan masalah ransel, dan entah bagaimana menyesuaikan solusi untuk memenuhi kendala yang diabaikan.

Aplikasi

Dalam banyak kasus alokasi sumber daya bersama dengan beberapa kendala, masalah dapat diturunkan dengan cara yang mirip dengan masalah Knapsack. Berikut ini adalah sekumpulan contoh.

Menemukan cara paling tidak boros untuk memotong bahan mentah
pengoptimalan portofolio
Memotong masalah stok

Skenario Masalah

Seorang pencuri merampok sebuah toko dan dapat membawa barang seberat maksimal Wke ranselnya. Ada n item yang tersedia di toko dan berati^th item adalah w_i dan keuntungannya p_i. Barang apa yang harus diambil pencuri?

Dalam konteks ini, barang-barang tersebut harus dipilih sedemikian rupa sehingga pencuri akan membawa barang-barang tersebut sehingga dia akan memperoleh keuntungan maksimal. Karenanya, tujuan pencuri adalah untuk memaksimalkan keuntungan.

Berdasarkan sifat itemnya, masalah Knapsack dikategorikan sebagai

Knapsack pecahan
Knapsack

Knapsack pecahan

Dalam hal ini, barang dapat dipecah menjadi potongan-potongan kecil, oleh karena itu pencuri dapat memilih pecahan barang.

Menurut pernyataan masalah,

Ada n item di toko
Berat i^th item $ w_ {i}> 0 $
Untung untuk i^th item $ p_ {i}> 0 $ dan
Kapasitas Knapsack adalah W

Dalam masalah Knapsack versi ini, item dapat dipecah menjadi potongan-potongan kecil. Jadi, pencuri hanya mengambil sebagian kecilx_i dari i^th barang.

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

Itu i^th item memberikan kontribusi bobot $ x_ {i} .w_ {i} $ ke total bobot di ransel dan keuntungan $ x_ {i} .p_ {i} $ ke total keuntungan.

Oleh karena itu, tujuan dari algoritma ini adalah untuk

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

tunduk pada kendala,

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

Jelas bahwa solusi optimal harus mengisi ransel dengan tepat, jika tidak, kita dapat menambahkan sebagian kecil dari salah satu item yang tersisa dan meningkatkan keuntungan secara keseluruhan.

Dengan demikian, solusi optimal dapat diperoleh

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

Dalam konteks ini, pertama-tama kita perlu mengurutkan item tersebut sesuai dengan nilai $ \ frac {p_ {i}} {w_ {i}} $, sehingga $ \ frac {p_ {i} +1} {w_ {i } +1} $ ≤ $ \ frac {p_ {i}} {w_ {i}} $. Sini,x adalah larik untuk menyimpan pecahan item.

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

Analisis

Jika item yang disediakan sudah disortir menjadi urutan menurun $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $, maka whileloop membutuhkan waktu O(n); Oleh karena itu, total waktu termasuk pengurutan masukO(n logn).

Contoh

Mari kita pertimbangkan kapasitas ransel itu W = 60 dan daftar item yang disediakan ditunjukkan pada tabel berikut -

Barang	SEBUAH	B	C	D
Keuntungan	280	100	120	120
Bobot	40	10	20	24
Rasio $ (\ frac {p_ {i}} {w_ {i}}) $	7	10	6	5

Karena item yang disediakan tidak diurutkan berdasarkan $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $. Setelah diurutkan, item-item tersebut akan ditampilkan pada tabel berikut.

Barang	B	SEBUAH	C	D
Keuntungan	100	280	120	120
Bobot	10	40	20	24
Rasio $ (\ frac {p_ {i}} {w_ {i}}) $	10	7	6	5

Larutan

Setelah menyortir semua item menurut $ \ frac {p_ {i}} {w_ {i}} $. Pertama-tamaB dipilih sebagai bobot Bkurang dari kapasitas ransel. Selanjutnya, itemA dipilih, karena kapasitas ransel yang tersedia lebih besar daripada beratnya A. Sekarang,Cdipilih sebagai item berikutnya. Namun, seluruh barang tidak dapat dipilih karena sisa kapasitas ransel kurang dari beratnyaC.

Karenanya, fraksi C (yaitu (60 - 50) / 20) dipilih.

Sekarang, kapasitas Knapsack sama dengan item yang dipilih. Karenanya, tidak ada lagi item yang dapat dipilih.

Berat total item yang dipilih adalah 10 + 40 + 20 * (10/20) = 60

Dan total keuntungannya 100 + 280 + 120 * (10/20) = 380 + 60 = 440

Ini adalah solusi optimal. Kami tidak dapat memperoleh lebih banyak keuntungan dengan memilih kombinasi item yang berbeda.