Knapsack

Ilustrasi: Online delivery

Budi adalah seorang driver Gobek yang bertugas untuk mengantar pesanan same-day service. Hari ini ada sejumlah paket di hadapan Budi, yang beratnya:

  • 5 kg
  • 4.7 kg
  • 4.3 kg
  • 3.8 kg
  • 3.1 kg
  • 3 kg
  • 2.5 kg
  • 1.4 kg
  • 0.8 kg

Kapasitas pengantaran per driver dibatasi sebesar 15 kg untuk menjaga kesehatan dan keamanan mereka.

Eksplorasi

  1. Paket mana yang harus dipilih Budi jika Budi ingin:
    1. membawa sebanyak mungkin dan seberat mungkin paket?
    2. membawa sebanyak mungkin tetapi seringan mungkin paket?
    3. membawa sesedikit mungkin tetapi seberat mungkin paket?
  2. Adakah algoritma umum untuk menentukan solusi persoalan ini?
  3. Jika selain berat ada batasan volume, apakah algoritmanya akan berbeda?
Ditulis oleh
Ari Prasetyo
Ditulis pada
Terakhir diupdate
Dipublikasikan
Frase kunci
kombinatorika