PENERAPAN ALGORITMA PEMROGRAMAN DINAMIS (DYNAMIC PROGRAMMING) PADA KNAPSACK PROBLEM

Penelitian ini menerapkan algoritma pemrograman dinamis (dynamic programming) untuk mengoptimalkan kombinasi barang dalam distribusi logistik berbasis permasalahan knapsack. Permasalahan utamanya adalah memilih barang dengan keuntungan optimal tanpa melampaui batas kapasitas kendaraan sebesar 865 kg. Melalui metode pembobotan prioritas, penelitian ini menganalisis bagaimana faktor berat dan nilai barang memengaruhi keputusan algoritma. Selain itu, juga mengidentifikasi faktor yang lebih dominan, serta mengetahui simulasi bobot terbaik yang mengoptimalkan keuntungan dan meminimalkan sisa kapasitas kendaraan. Data simulasi yang digunakan mencakup 45 jenis barang furnitur dan elektronik rumah tangga dengan karakteristik berat dan nilai yang bervariasi. Penelitian ini menguji 11 simulasi pembobotan prioritas antara faktor nilai dan berat dengan rentang kombinasi 75%; 25% hingga 25%;75% (interval 5%) menggunakan bahasa Python di platform Google Colaboratory. Berdasarkan hasil penelitian, algoritma pemrograman dinamis secara dominan dipengaruhi oleh faktor nilai. Peningkatan bobot faktor nilai pada fungsi tujuan berbanding lurus dengan kenaikan total potensi keuntungan yang diperoleh. Potensi keuntungan tertinggi yang diperoleh sebesar 46,9% pada simulasi nilai 75% dan berat 25%. Karakteristik algoritma ini membuat barang bernilai tinggi seperti lemari pakaian dua pintu, rak server, kulkas satu pintu, dan mesin kopi espresso konsisten masuk dalam kombinasi terpilih. Penelitian ini berhasil membuktikan bahwa algoritma pemrograman dinamis efektif menyelesaikan masalah knapsack dalam distribusi logistik melalui 11 simulasi pembobotan prioritas yang komperhensif. Berdasarkan hasil analisis terhadap seluruh simulasi, penentuan kombinasi paling optimal tidak dapat ditentukan secara kaku pada simulasi tertentu. Pilihan simulasi terbaik pada akhirnya bersifat fleksibel dan sangat bergantung pada kondisi pasar – apakah sedang memprioritaskan target keuntungan tinggi atau efisiensi keselamatan kendaraan.
Kata kunci : permasalahan knapsack, pembobotan, pemrograman dinamis