Kullanılan kutular
Alt sınır
Mümkün olan en az

      Nesne ağırlıkları (kg)

        Kutu paketleme problemi hakkında daha fazla

        Kutu paketleme problemi

        Kolileri kamyonete, dosyaları disklere, işleri makinelere: kutu paketleme problemi, bir nesne listesinin olabildiğince az sayıda eşit kutuya nasıl sığdırılacağını sorar. Her zaman en iyi yerleşimi bulan hızlı bir yöntem bilinmiyor, ama basit kurallar epey yaklaşır. Bir kural seçin, adım adım izleyin ve kesin cevapla karşılaştırın. Raftaki bir nesneye, sonra onu koymak istediğiniz kutuya dokunun: yeşil kutularda ona yer var, Yeni kutu ise bir kutu daha açar. Kutudaki bir nesneye dokunarak onu yeniden çıkarın. Tüm nesneleri olabildiğince az kutuya yerleştirin; alt sınır (toplam ağırlığın kutu boyutuna bölümü, yukarı yuvarlanmış) ve mümkün olan en az sayı ne kadar yaklaştığınızı gösterir, En az kutu ise en iyi yerleşimi gösterir. Paneldeki nesne ağırlıklarını (kilogram olarak) ve kutu boyutunu değiştirin. Adım adım görünümü hızlı kuralların nasıl yerleştirdiğini gösterir: sonraki uyan, ilk uyan veya en iyi uyan, nesneler yazıldığı sırayla ya da büyükten küçüğe sıralanmış olarak; ya da dinamik programlamanın bulduğu kesin cevap. Nesnelerin kutulara girişini izlemek için Oynat'a, adım adım ilerlemek için Adım ve Geri'ye basın; istediğiniz yere atlamak için adım kaydırıcısını sürükleyin. Tahta seçiliyken ok tuşları adım adım ilerletir, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.

        Nasıl çalışır

        1. Bir eşyaya, ardından onu koymak için yeri olan bir kutuya dokunun ya da yeni bir kutu açmak için Yeni kutu düğmesine dokunun.
        2. Olabildiğince az kutu kullanmaya çalışın ya da en iyi yerleşimi görmek için En az kutu düğmesine basın.
        3. Adım adım görünümünü açın, bir kural seçin ve her eşyanın kutuları nasıl denediğini izlemek için Oynat'a basın.

        Kurallar

        Sonraki uyan yalnızca son kutuyu açık tutar: oraya sığmayan bir nesne yeni bir kutu başlatır. İlk uyan kutuları baştan itibaren dener ve yeri olan ilk kutuyu seçer. En iyi uyan tüm kutuları dener ve yeri olan en dolu kutuyu seçer; böylece en az boş alan kalır. İlk uyan ve en iyi uyan, nesneleri önce büyükten küçüğe de sıralayabilir; bu da azalan ilk uyan ve azalan en iyi uyanı verir.

        Kesin cevap

        Son kural bir pratik kural değildir: en az kutuyu, nesne kümeleri üzerinde dinamik programlamayla bulur. Her nesne kümesi için onları alan en az kutu sayısını ve bu sayıda kutu kullanan yerleşimler arasında son kutudaki en küçük yükü saklar. Bir küme her seferinde bir nesne büyür; bu nesne ya son kutuya eklenir ya da yeni bir kutu açar. n nesneyle 2ⁿ küme vardır; uygulamanın en fazla 12 nesneye izin vermesinin nedeni budur. Alt sınır, yani toplam boyutun kutu boyutuna bölünüp yukarı yuvarlanması, bir yerleşimin en iyiye ne kadar yakın olduğunu gösterir.

        Sık sorulan sorular

        Hangi kutu paketleme kuralı en iyisi?

        Hızlı kurallar arasında en güçlüleri azalan ilk uyan ve azalan en iyi uyandır: hiçbir zaman en az kutu sayısının 11/9 katı artı küçük bir sabitten fazla kutu kullanmazlar. Sıralanmamış nesnelerde ilk uyan ve en iyi uyan en az kutu sayısının 1,7 katı içinde, sonraki uyan ise 2 katı içinde kalır.

        Kutu paketleme neden zor?

        Nesnelerin yalnızca iki kutuya sığıp sığmadığına karar vermek bile NP-tam olan bölüntü (partition) problemidir. Bu yüzden P = NP olmadıkça hiçbir yöntem her girdi için en az kutuyu hızlıca bulamaz ve kesin yöntemler en kötü durumda üstel zaman alır.

        Alt sınır nedir?

        Nesnelerin toplam boyutunun kutu boyutuna bölünüp yukarı yuvarlanmış hâlidir. Hiçbir yerleşim daha az kutu kullanamaz, çünkü kutuların tüm nesneleri alması gerekir. Çoğu zaman en iyi yerleşim buna eşittir ama her zaman değil: 10 boyutundaki kutularla 6 boyutunda üç nesnenin alt sınırı 2'dir, ama 3 kutu gerekir.

        Bu dinamik programlama mı?

        Kesin cevap öyle: her nesne kümesi için en iyi yerleşimi daha küçük kümelerin en iyi yerleşimlerinden kurar. Hızlı kurallar ise açgözlü yöntemlerdir; bir kez karar verir ve asla geri dönmezler.

        Herhangi bir yere bir şey gönderiliyor mu?

        Hayır. Her şey tarayıcınızda hesaplanır ve son ayarlarınız bu tarayıcının yerel depolamasında kalır.

        Denemeye hazır mısınız?

        PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

        Editöre Git