Pengertian
knapsack = karung, kantung, buntilan
Problem :
Diberikan n buah objek dan sebuah knapsack dengan kapasitas tertentu (K). Setiap objek memilki property bobot w(weight) dan keuntungan p(profit). Objektif persoalan adalah bagaimana memilih objek-objek yang dimasukkan ke dalam knapsack sehingga tidak melebihi kapasitas knapsack namun memaksimumkan total keuntungan yang diperoleh.”
Langkah -langkahnya adalah:
Contoh soal
Tinjau persoalan 0/1 Knapsack dengan n = 4. Misalkan objek-objek tersebut kita beri nomor 1, 2, 3, dan 4. Properti setiap objek i dan kapasitas knapsack adalah sebagai berikut
w1 = 2; p1 = 20
w2 = 5; p1 = 30
w3 = 10; p1 = 50
w4 = 5; p1 = 10
Kapasitas knapsack W = 16
Langkah-langkah pencarian solusi 0/1 Knapsack secara exhaustive search dirangkum dalam tabel di bawah ini:
knapsack = karung, kantung, buntilan
Problem :
Diberikan n buah objek dan sebuah knapsack dengan kapasitas tertentu (K). Setiap objek memilki property bobot w(weight) dan keuntungan p(profit). Objektif persoalan adalah bagaimana memilih objek-objek yang dimasukkan ke dalam knapsack sehingga tidak melebihi kapasitas knapsack namun memaksimumkan total keuntungan yang diperoleh.”
Langkah -langkahnya adalah:
- Misalkan terdapat n objek yang memiliki profit dan berat masing-masing Dan kapasitas knapsack sebanyak Maks.
- Cari himpunan bagian dari n objek
- Uji jumlah berat dari himpunan bagian tersebut. Jika beratnya melebihi kapasitas, kembali ke nomor 2. Jika tidak, lanjut ke nomer 3
- Uji jumlah profit dari himpunan bagian tersebut. Jika profitnya melebihi profit maksimal sementara, simpan profit baru sebagai profit maksimal dan himpunan bagiannya. Jika tidak, kembali ke nomor 2.
- Jika seluruh himpunan bagian sudah diuji, himpunan bagian dengan profit maksimal terakhir adalah solusi terbaik dari knapsack
Contoh soal
Tinjau persoalan 0/1 Knapsack dengan n = 4. Misalkan objek-objek tersebut kita beri nomor 1, 2, 3, dan 4. Properti setiap objek i dan kapasitas knapsack adalah sebagai berikut
w1 = 2; p1 = 20
w2 = 5; p1 = 30
w3 = 10; p1 = 50
w4 = 5; p1 = 10
Kapasitas knapsack W = 16
Langkah-langkah pencarian solusi 0/1 Knapsack secara exhaustive search dirangkum dalam tabel di bawah ini:
- Himpunan bagian objek yang memberikan keuntungan maksimum adalah {2, 3} dengan total keuntungan adalah 80.
- Solusi persoalan 0/1 Knapsack di atas adalah X = {0, 1, 1, 0}
- Berapa banyak himpunan bagian dari sebuah himpunan dengan n elemen? Jawab adalah 2n. Ini berarti, algoritma exhaustive search untuk persoalan 0/1 Knapsack mempunyai kompleksitas O(2n).
- 0/1 Knapsack adalah contoh persoalan yang mempunyai kompleksitas algoritma eksponensial. Knapsack digolongkan sebagai persoalan NP (Non-deterministic Polynomial), karena tidak mungkin dapat ditemukan algoritma polinomial untuk memecahkannya.
| Himpunan Bagian | Total Bobot | Total keuntungan |
| {} {1} {2} {3} {4} {1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4} {1, 2, 3} {1, 2, 4} {1, 3, 4} {2, 3, 4} {1, 2, 3, 4} | 0 2 5 10 5 7 12 7 15 10 15 17 12 17 20 22 | 0 20 30 50 10 50 70 30 80 40 60 tidak layak 60 tidak layak tidak layak tidak layak |
0 komentar:
Posting Komentar