Wadah terpakai
Batas bawah
Paling sedikit

      Berat barang (kg)

        Selengkapnya tentang masalah bin packing

        Masalah bin packing

        Kardus ke dalam mobil boks, berkas ke dalam disk, pekerjaan ke dalam mesin: masalah bin packing menanyakan cara memasukkan daftar barang ke dalam wadah berukuran sama sesedikit mungkin. Belum ada metode cepat yang diketahui selalu menemukan pengemasan terbaik, tetapi aturan sederhana bisa mendekatinya. Pilih aturan, jalankan langkah demi langkah, dan bandingkan dengan jawaban pasti. Ketuk barang di rak, lalu ketuk wadah untuk memasukkannya: wadah hijau masih muat untuknya, dan Wadah baru membuka satu wadah lagi. Ketuk barang di dalam wadah untuk mengeluarkannya lagi. Kemas semua barang ke dalam wadah sesedikit mungkin; batas bawah (berat total dibagi ukuran wadah, dibulatkan ke atas) dan jumlah paling sedikit yang mungkin menunjukkan seberapa dekat Anda, dan Wadah paling sedikit menunjukkan pengemasan terbaik. Ubah berat barang (dalam kilogram) dan ukuran wadah di panel. Tampilan Langkah demi langkah menunjukkan cara aturan cepat mengemas: next fit, first fit, atau best fit, pada barang sesuai urutan ketikan atau diurutkan dari yang terbesar, atau jawaban pasti yang ditemukan pemrograman dinamis. Tekan Putar untuk melihat barang masuk ke wadah, atau Langkah dan Mundur untuk bergerak satu langkah demi satu langkah, dan seret penggeser langkah untuk melompat ke mana saja. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.

        Cara kerjanya

        1. Ketuk sebuah barang, lalu ketuk wadah yang masih muat untuk memasukkannya, atau Wadah baru untuk membuka wadah lain.
        2. Coba gunakan wadah sesedikit mungkin, atau tekan Wadah paling sedikit untuk melihat pengemasan terbaik.
        3. Buka tampilan Langkah demi langkah, pilih aturan, dan tekan Putar untuk melihat setiap barang mencoba wadah-wadahnya.

        Aturan-aturannya

        Next fit hanya membiarkan wadah terakhir terbuka: barang yang tidak muat di sana memulai wadah baru. First fit mencoba wadah dari yang pertama dan memilih wadah pertama yang masih muat. Best fit mencoba semua wadah dan memilih wadah terpenuh yang masih muat, sehingga ruang yang tersisa paling sedikit. First fit dan best fit juga bisa mengurutkan barang dari yang terbesar ke terkecil lebih dulu, yang menghasilkan first fit decreasing dan best fit decreasing.

        Jawaban pasti

        Aturan terakhir bukan aturan praktis: aturan ini menemukan jumlah wadah paling sedikit dengan pemrograman dinamis atas himpunan barang. Untuk setiap himpunan barang, disimpan jumlah wadah paling sedikit yang dapat menampungnya dan, di antara pengemasan dengan jumlah wadah itu, muatan terkecil di wadah terakhir. Himpunan bertambah satu barang setiap kali, dan barang itu menambah isi wadah terakhir atau membuka wadah baru. Dengan n barang ada 2ⁿ himpunan, karena itu aplikasi ini mengizinkan paling banyak 12 barang. Batas bawah, yaitu ukuran total dibagi ukuran wadah lalu dibulatkan ke atas, menunjukkan seberapa dekat suatu pengemasan dengan yang terbaik.

        Pertanyaan yang sering diajukan

        Aturan bin packing mana yang terbaik?

        Di antara aturan cepat, first fit decreasing dan best fit decreasing yang paling kuat: keduanya tidak pernah memakai lebih dari 11/9 jumlah wadah paling sedikit, ditambah konstanta kecil. First fit dan best fit pada barang yang tidak diurutkan tetap dalam batas 1,7 kali jumlah wadah paling sedikit, dan next fit dalam batas 2 kali.

        Mengapa bin packing sulit?

        Menentukan apakah barang-barang muat dalam dua wadah saja sudah merupakan masalah partisi, yang NP-complete. Jadi, kecuali P = NP, tidak ada metode yang menemukan jumlah wadah paling sedikit dengan cepat untuk setiap masukan, dan metode pasti memerlukan waktu eksponensial dalam kasus terburuk.

        Apa itu batas bawah?

        Ukuran total barang dibagi ukuran wadah, dibulatkan ke atas. Tidak ada pengemasan yang bisa memakai wadah lebih sedikit, karena wadah harus menampung semua barang. Sering kali pengemasan terbaik sama dengan batas bawah, tetapi tidak selalu: tiga barang berukuran 6 dengan wadah berukuran 10 punya batas bawah 2, tetapi butuh 3 wadah.

        Apakah ini pemrograman dinamis?

        Jawaban pastinya ya: jawaban itu membangun pengemasan terbaik untuk setiap himpunan barang dari pengemasan terbaik himpunan yang lebih kecil. Aturan cepat adalah metode greedy, yang memutuskan sekali dan tidak pernah menoleh ke belakang.

        Apakah ada yang dikirim ke suatu tempat?

        Tidak. Semuanya dihitung di browser Anda, dan pengaturan terakhir Anda tersimpan di penyimpanan lokal browser ini.

        Siap mencobanya?

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

        Ke Editor