DAA - 0-1 Knapsack

Dalam tutorial ini, sebelumnya kita telah membahas masalah Fractional Knapsack dengan menggunakan pendekatan Greedy. Kami telah menunjukkan bahwa pendekatan Greedy memberikan solusi optimal untuk Fractional Knapsack. Namun, bab ini akan membahas masalah Knapsack 0-1 dan analisisnya.

Dalam Knapsack 0-1, item tidak bisa dipecahkan yang berarti pencuri harus mengambil item tersebut secara keseluruhan atau harus meninggalkannya. Inilah alasan dibalik menyebutnya sebagai Knapsack 0-1.

Oleh karena itu, dalam kasus Knapsack 0-1, nilai xi bisa juga 0 atau 1, di mana batasan lainnya tetap sama.

0-1 Knapsack tidak bisa diselesaikan dengan pendekatan Greedy. Pendekatan serakah tidak menjamin solusi yang optimal. Dalam banyak kasus, pendekatan Greedy dapat memberikan solusi yang optimal.

Contoh berikut akan membentuk pernyataan kami.

Contoh 1

Mari kita pertimbangkan bahwa kapasitas ransel adalah W = 25 dan itemnya seperti yang ditunjukkan pada tabel berikut.

Barang SEBUAH B C D
Keuntungan 24 18 18 10
Bobot 24 10 10 7

Tanpa mempertimbangkan keuntungan per satuan berat (pi/wi), jika kita menerapkan pendekatan Greedy untuk menyelesaikan masalah ini, item pertama Aakan dipilih karena akan memberikan kontribusi max i keuntungan ibu di antara semua elemen.

Setelah memilih item A, tidak ada lagi item yang akan dipilih. Oleh karena itu, untuk kumpulan item ini, total keuntungan adalah24. Sedangkan solusi optimal dapat dicapai dengan memilih item,B dan C, dengan total keuntungan 18 + 18 = 36.

Contoh-2

Alih-alih memilih item berdasarkan manfaat keseluruhan, dalam contoh ini item dipilih berdasarkan rasio p i / w i . Mari kita pertimbangkan bahwa kapasitas ransel adalah W = 60 dan itemnya seperti yang ditunjukkan pada tabel berikut.

Barang SEBUAH B C
Harga 100 280 120
Bobot 10 40 20
Perbandingan 10 7 6

Menggunakan pendekatan Greedy, item pertama Adipilih. Lalu, item berikutnyaBterpilih. Karenanya, total keuntungan adalah100 + 280 = 380. Namun, solusi optimal dari contoh ini dapat dicapai dengan memilih item,B dan C, dimana keuntungan totalnya 280 + 120 = 400.

Dengan demikian, dapat disimpulkan bahwa pendekatan Greedy belum tentu memberikan solusi yang optimal.

Untuk menyelesaikan Knapsack 0-1, diperlukan pendekatan Dynamic Programming.

Pernyataan masalah

Seorang pencuri yang merampok toko dan dapat membawa max i berat mal dariWke ranselnya. Adan barang dan berat ith item adalah wi dan keuntungan memilih item ini pi. Barang apa yang harus diambil pencuri?

Pendekatan Pemrograman Dinamis

Membiarkan i menjadi item dengan nomor tertinggi dalam solusi optimal S untuk Wdolar. KemudianS' = S - {i} adalah solusi optimal untuk W - wi dolar dan nilai solusi S adalah Vi ditambah nilai sub-masalah.

Fakta ini dapat kita ekspresikan dalam rumus berikut: define c[i, w] menjadi solusi untuk barang 1,2, … , idan max i berat badan ibuw.

Algoritme mengambil masukan berikut

  • Max i berat badan ibuW

  • Jumlah item n

  • Dua urutan v = <v1, v2, …, vn> dan w = <w1, w2, …, wn>

Dynamic-0-1-knapsack (v, w, n, W) 
for w = 0 to W do 
   c[0, w] = 0 
for i = 1 to n do 
   c[i, 0] = 0 
   for w = 1 to W do 
      if wi ≤ w then 
         if vi + c[i-1, w-wi] then 
            c[i, w] = vi + c[i-1, w-wi] 
         else c[i, w] = c[i-1, w] 
      else 
         c[i, w] = c[i-1, w]

Kumpulan item yang akan diambil dapat disimpulkan dari tabel, mulai dari c[n, w] dan menelusuri ke belakang dari mana nilai optimal berasal.

Jika c [i, w] = c [i-1, w] , maka itemi bukan bagian dari solusi, dan kami terus menelusuri c[i-1, w]. Jika tidak, itemi adalah bagian dari solusi, dan kami terus menelusuri c[i-1, w-W].

Analisis

Algoritma ini membutuhkan θ ( n , w ) kali karena tabel c memiliki entri ( n + 1). ( W + 1), di mana setiap entri membutuhkan θ (1) waktu untuk menghitung.