Biarkan menjadi seperangkat bentuk persegi panjang dimensional. Untuk dan , menjelaskan panjang dalam dimensi . Notasi yang sama digunakan untuk wadah . Masalah pengemasan orthogonal dimensional (OPP- ) adalah memutuskan apakah cocok dengan wadah tanpa tumpang tindih. Secara formal, masalahnya adalah untuk mengetahui apakah ada fungsi , sehingga dan , , .
Masalahnya adalah NP-lengkap (lihat Fekete SP, Schepers J. "Pada pengemasan dimensi tinggi I: Modeling". Laporan Teknis 97-288, Universitas di zu Köln, 1997). Masalahnya adalah NP-lengkap bahkan untuk . Saya bertanya-tanya, apakah masalah pengemasan ortogonal untuk jumlah jenis yang terbatas (yaitu ukuran di setiap dimensi) item masih lengkap atau tidak NP. Sampai sekarang saya menemukan hasil di beberapa makalah tentang NP-kelengkapan kotak pengemasan menjadi persegi (lihat JOSEPH YT. LEUNG, TOMMY W. TAM, DAN CS WONG, "Pengemasan kotak menjadi kotak", Journal of Parallel and Distributed Computing, Volume 10 Edisi 3, November 1990) yang sudah menjadi batasan tetapi saya masih tidak tahu apa yang terjadi ketika jumlah jenis barang dibatasi.
Terima kasih atas jawaban Anda,
Jawaban:
Saya pikir makalah yang ditulis oleh Klaus Jansen dan Roberto Solis-Oba " Algoritma OPT + 1 untuk Masalah Stok dengan Jumlah Konstan Panjang Objek " memiliki jawaban parsial untuk pertanyaan Anda. Mereka menganggap kasus khusus masalah Anda yang dikenal sebagai masalah Pemotongan Stok ketika jumlah jenis objek yang berbeda konstan dan didefinisikan sebagai berikut:
Penulis mengklaim itu
Dan mereka mengusulkan pendekatan polinomial-waktu algoritma ketika diperbaiki.OPT+1 d
Karena tidak terbukti bahwa kasus khusus ini dalam , ini adalah bukti bahwa masalah Anda adalah .P NP
Addendum: itu dikenal bahwa kasus dengan dua jenis objek ( ) adalah polynomially dipecahkan, tetapi untuk ada hanya diketahui -approximation.d=2 d=3 OPT+1
sumber