Sekilas
Untuk soal
knapsack kali ini saya beranggapan bahwa ada 3 parameter dimana algoritma
greedy akan mencari dan menentukan berdasarkan apa dia mengambil nilai terbaik di setiap langkahnya. Parameter tersebut meliputi : bobot, profit, dan profit/bobot. Yang bisa dilihat pada list berikut:
item = [[3,4],[4,5],[1,2],[7,5],[6,5],[8,8],[9,11]]
pada list item berbentuk 7 x 2. Yang artinya ada 7 baris dan 2 kolom. Baris melambangkan banyaknya nilai. Kolom ke-1 melambangkan bobot, kolom ke-2 melambangkan profit. Kita akan mencari profit optimum berdasarkan algoritma greedy tadi dengan Kapasitas sistemnya adalah 20.
Pengerjaan Manual
Code Phyton 3.6
Running Program dan Hasil
Sumber :
Lokasi:
ini kenapa urutan datanya harus dibalik?
BalasHapusreverse = True ?
Hapusditunjukkan untuk mengurutkan data pi dari yang paling besar terlebih dahulu.
Mengapa harus diurut mulai yg terbesar?
Hapusmemang kurang lebih seperti itu jadi data yang bobotnya besar akan digunakan terlebih dahulu
Hapusmisalkan kita menggunakan bobot maksimal dengan kapasitas 20kg diperoleh keuntungan 23ribu , kemudian jika menggunakan nilai prioritas
BalasHapusmaka nilai yang kita dapatakan adalah 22, nah nilai 22 tersebut termasuk dalam satuan apa?
lebih ke satuan bobot knapsacknya. Sejujurnya code ini dibuat untuk kasus optimum lokal saja (pendekatan greedy). Jadi nilai 22 itu melambangkan nilai bobot semu yang menjadi acuan kenapa data tersebut dipilih (urutannya itu dulu). Apakah mungkin ada optimum lain ? bisa jadi ada.
HapusJadi nilai 22 hanya sebagai nilai acuan saja, bahwa ada nilai yg lebih optimum dari nilai optimum berat atau profit. Apakah betul seperti itu?
HapusIya kurang lebih seperti itu (sisanya mungkin bisa dicari di referensi lain)
Hapus