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 x_i 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 (p_i/w_i), 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 i^th item adalah w_i dan keuntungan memilih item ini p_i. 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 - w_i dolar dan nilai solusi S adalah V_i 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 = <v₁, v₂, …, v_n> dan w = <w₁, w₂, …, w_n>

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.