Penyelesaian Knapsack Problem Menggunakan Algoritma Greedy

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 :



8 komentar untuk "Penyelesaian Knapsack Problem Menggunakan Algoritma Greedy"

  1. ini kenapa urutan datanya harus dibalik?

    BalasHapus
    Balasan
    1. reverse = True ?

      ditunjukkan untuk mengurutkan data pi dari yang paling besar terlebih dahulu.

      Hapus
    2. Mengapa harus diurut mulai yg terbesar?

      Hapus
    3. memang kurang lebih seperti itu jadi data yang bobotnya besar akan digunakan terlebih dahulu

      Hapus
  2. misalkan kita menggunakan bobot maksimal dengan kapasitas 20kg diperoleh keuntungan 23ribu , kemudian jika menggunakan nilai prioritas
    maka nilai yang kita dapatakan adalah 22, nah nilai 22 tersebut termasuk dalam satuan apa?

    BalasHapus
    Balasan
    1. 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.

      Hapus
    2. Jadi nilai 22 hanya sebagai nilai acuan saja, bahwa ada nilai yg lebih optimum dari nilai optimum berat atau profit. Apakah betul seperti itu?

      Hapus
    3. Iya kurang lebih seperti itu (sisanya mungkin bisa dicari di referensi lain)

      Hapus

Berilah komentar, saran, dan kritik dengan bijak