knapsack

ransel

Masalah knapsack adalah masalah optimasi yang terkenal. Hal ini ditemui, misalnya, dalam pengepakan kontainer pengiriman. Sebuah kontainer pengiriman memiliki kapasitas berat yang dapat ditampungnya. Mengingat kumpulan barang yang akan dikirim, dimana setiap barang memiliki nilai dan berat, maka permasalahannya adalah memilih barang yang optimal untuk dikemas dalam kontainer pengiriman. Masalah optimasi ini dapat didefinisikan sebagai suatu tujuan dengan batasan:

• Tujuan: Memaksimalkan nilai pengangkutan (jumlah nilai barang yang dipilih).
• Batasan: Total berat angkutan (jumlah berat barang yang dipilih) harus kurang dari atau sama dengan kapasitas kontainer.

Contoh ini memecahkan masalah knapsack dengan memformulasikannya kembali sebagai model kuadrat terbatas (CQM) dan mengirimkannya ke pemecah Leap hybrid CQM.

Penggunaan

Untuk menjalankan demo default, masukkan perintah:

python knapsack.py

Untuk melihat opsi yang tersedia, masukkan perintah:

python knapsack.py --help

Argumen baris perintah memungkinkan Anda memilih salah satu dari beberapa kumpulan data (di bawah folder /data ) dan mengatur kapasitas pengangkutan. File data dirumuskan sebagai baris item, masing-masing didefinisikan sebagai pasangan bobot dan nilai.

Ikhtisar Kode

Kode di knapsack.py mencakup tiga fungsi utama:

• build_knapsack_cqm() membuat CQM dengan menetapkan tujuan dan batasan sebagai berikut:

  • Tujuan: Variabel biner dibuat untuk setiap item, dan diberi bias linier yang sama dengan nilai negatif dari nilai item tersebut. Untuk meminimalkan tujuan ini, dengan memilih kumpulan barang yang optimal, setara dengan memaksimalkan nilai total barang. Solusi menetapkan nilai 1 untuk item yang dipilih dan 0 untuk item yang tidak dipilih.
  • Batasan: Model kuadrat dengan variabel biner yang dibuat sebelumnya, di mana bias linier ditetapkan sama dengan bobot setiap item, dibuat dengan persyaratan bahwa bobot total tidak boleh melebihi kapasitas wadah.

• parse_inputs() adalah fungsi utilitas yang membaca data dari file contoh.

• parse_solution() mem-parsing dan menampilkan hasil yang dikembalikan dari solver.

Lisensi

Dirilis di bawah Lisensi Apache 2.0. Lihat file LISENSI.