Masalah bin packing

Saat pindah rumah, Anda mengisi kardus satu demi satu dan bertanya-tanya apakah urutan yang lebih cerdik akan membutuhkan lebih sedikit kardus. Itulah masalah bin packing, dan masalah ini terkenal sulit: bahkan komputer hanya bisa menemukan jumlah wadah paling sedikit untuk masukan besar dengan pencarian yang cerdik. Namun, aturan sederhana ternyata bisa sangat mendekati.

Wadah-wadah setinggi sama berisi tumpukan barang berwarna dengan berbagai ukuran, dengan barang lain menunggu di atasnya
Wadah-wadah setinggi sama berisi tumpukan barang berwarna dengan berbagai ukuran, dengan barang lain menunggu di atasnya

Masalahnya

Diberikan barang-barang dengan ukuran tertentu dan wadah-wadah yang masing-masing menampung jumlah yang sama, masukkan setiap barang ke sebuah wadah sehingga tidak ada wadah yang meluap, dengan wadah sesedikit mungkin. Ukuran bisa mewakili berat, panjang, durasi, atau ukuran berkas. Kedengarannya seperti teka-teki untuk sore yang hujan, tetapi masalah ini NP-hard: belum ada metode yang diketahui dapat menemukan jumlah wadah paling sedikit dengan cepat untuk setiap masukan.

Aturan cepat

Next fit mengisi satu wadah sampai barang berikutnya tidak muat, lalu memulai wadah baru dan tidak pernah menoleh ke belakang. First fit membiarkan semua wadah terbuka dan memasukkan setiap barang ke wadah pertama yang masih muat. Best fit memasukkan setiap barang ke wadah terpenuh yang masih punya ruang. Ketiganya langsung memutuskan, yang berguna saat barang datang satu per satu dan harus segera ditempatkan.

Urutkan dulu

Barang besar adalah yang sulit, karena butuh banyak ruang kosong. Mengurutkan barang dari yang terbesar ke terkecil lalu memakai first fit atau best fit akan memasukkan barang besar selagi wadah masih kosong, lalu mengisi celahnya dengan barang kecil. First fit decreasing tidak pernah memakai lebih dari 11/9 jumlah wadah paling sedikit, ditambah sebuah konstanta, dibandingkan 1,7 kali untuk first fit pada barang yang tidak diurutkan.

Sebuah contoh

Ambil wadah berukuran 10 dan barang 2, 3, 2, 1, 3, 4, 5, 6, 7, dan 7, yang jumlahnya 40. First fit memasukkan 2, 3, 2, dan 1 ke wadah pertama serta 3 dan 4 ke wadah kedua, lalu 5, 6, 7, dan 7 masing-masing butuh wadah sendiri: 6 wadah. Setelah diurutkan dari yang terbesar, first fit decreasing membuat 7 + 3, 7 + 3, 6 + 4, dan 5 + 2 + 2 + 1: 4 wadah penuh, sama dengan batas bawah 40 / 10 = 4.

Mencari wadah paling sedikit

Untuk sedikit barang, jawaban pasti dapat ditemukan dengan pemrograman dinamis atas himpunan bagian: untuk setiap himpunan barang, jumlah wadah paling sedikit dan wadah terakhir paling kosong yang menampungnya dibangun dari himpunan yang kurang satu barang. Itu memerlukan sekitar 2ⁿ·n langkah untuk n barang. Kasus yang lebih besar diselesaikan dengan branch and bound atau pemrograman bilangan bulat, dan batas bawah menunjukkan seberapa jauh suatu pengemasan bisa dari yang terbaik.

Di mana digunakan

Memuat truk dan kontainer, memotong pipa atau gulungan kertas dari panjang standar dengan sisa sesedikit mungkin (cutting stock problem), menempatkan mesin virtual ke server, dan menyimpan berkas ke disk semuanya adalah masalah bin packing. Dalam dua dan tiga dimensi, dengan kotak alih-alih angka, masalahnya lebih sulit lagi.

Pertanyaan yang sering diajukan

Apa beda bin packing online dan offline?

Secara online, setiap barang harus ditempatkan begitu datang, tanpa mengetahui sisanya; next fit, first fit, dan best fit bekerja seperti itu. Secara offline, semua barang sudah diketahui sebelumnya, sehingga bisa diurutkan dulu, seperti yang dilakukan first fit decreasing.

Seberapa dekat first fit decreasing dengan hasil terbaik?

Paling banyak memakai 11/9 jumlah wadah paling sedikit ditambah 6/9 wadah, batas yang dibuktikan tepat oleh György Dósa pada 2007. Pada masukan biasa, hasilnya umumnya optimal atau hanya selisih satu wadah.

Apakah bin packing sama dengan masalah knapsack?

Keduanya berkaitan tetapi berbeda. Knapsack mengisi satu tas dengan barang paling berharga; bin packing memasukkan setiap barang ke tas sesedikit mungkin. Pemecah bin packing yang pasti sering bekerja dengan menyelesaikan masalah mirip knapsack berulang-ulang.

Mengapa aplikasi ini hanya mengizinkan 12 barang?

Karena jawaban pasti memeriksa setiap himpunan barang, dan 12 barang saja sudah menghasilkan 4.096 himpunan. Aturan cepat sanggup menangani ribuan barang, tetapi gambar dan perbandingan dengan jawaban pasti tidak.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Coba bin packing