Apa kompleksitas pengemasan segi empat saat rotasi diizinkan?

Dalam masalah persegi panjang packing, satu diberikan satu set empat persegi panjang dan berlari persegi panjang . Tugasnya adalah menemukan penempatan di dalam sedemikian rupa sehingga tidak ada persegi panjang yang tumpang tindih. Secara umum, orientasi setiap persegi panjang adalah tetap. Yaitu, persegi panjang tidak dapat diputar. Dalam kasus ini, masalahnya dikenal sebagai NP-complete (lihat, misalnya, Korp 2003 ).$\{r_1,\dots,r_n\}$$R$$r_1,\ldots,r_n$$R$$n$$r_i$

Apa kerumitan masalah pengemasan segi empat jika persegi panjang dapat diputar derajat?$90$

Secara intuitif, membiarkan rotasi hanya akan membuat masalah lebih sulit karena pertama-tama kita harus memilih orientasi untuk setiap persegi panjang, dan kemudian menyelesaikan masalah pengemasan tanpa rotasi. Tetapi bukti NP-hardness dari kasus no-rotation adalah pengurangan dari bin-packing dan tampaknya sangat tergantung pada orientasi tetap dari masing-masing persegi panjang untuk membangun tempat sampah. Saya belum dapat menemukan bukti kekerasan NP yang sesuai untuk kasus di mana rotasi diperbolehkan.

Kita dapat mengurangi masalah pengemasan tanpa rotasi ke masalah pengemasan yang diizinkan rotasi sebagai berikut. Ambil contoh dari masalah tanpa-rotasi. Vertikal skala seluruh misalnya dengan dua kali rasio lebar terkecil dari setiap persegi panjang r i dibagi dengan ketinggian wadah persegi panjang R . (Rasio ini memiliki jumlah bit polinomial, sehingga transformasi dapat dieksekusi dalam waktu polinomial.) Setiap persegi panjang berskala r $(R, r_1, r_2, \dots, r_n)$$r_i$$R$ pas di dalam wadah berskala R ′ hanya dalam orientasi aslinya, sehingga memungkinkan rotasi tidak menambah solusi baru.$r'\!\!_i$$R'$