Algoritma untuk mengatur pengemasan

Tampaknya ada banyak pekerjaan, untuk beberapa masalah NP-Hard, pada pengembangan algoritma tepat waktu eksponensial cepat (yaitu, hasil dari bentuk: Algoritma A memecahkan masalah dalam waktu O (c ^ n), dengan c kecil). Sepertinya ada cukup banyak pekerjaan di sepanjang garis-garis ini untuk beberapa masalah NP-keras (misalnya, Ukur dan menaklukkan: sederhana O ( 2 0,288 n ) . Algoritma set independen SODA'06 ) tapi saya belum bisa menemukan pekerjaan serupa untuk masalah pengepakan yang ditetapkan. Tampaknya ada pekerjaan serupa pada beberapa pembatasan masalah set kemasan (misalnya, An O * ( 3,523 k$x$$O(2^{0.288n})$$O^{*}(3.523^{k})$ Algoritma Parameter untuk Pengemasan 3-Set) tetapi saya belum menemukan masalah pengemasan set umum.

Jadi pertanyaan saya adalah: Apa kompleksitas waktu terbaik untuk memecahkan masalah pengepakan set tertimbang di mana ada set diambil dari alam semesta n elemen?$m$$n$

Saya juga tertarik pada hubungan antara jumlah set dan ukuran alam semesta. Misalnya, apakah sudah ada kerja algoritmik pada situasi di mana relatif besar dibandingkan dengan n (yaitu, mendekati 2 n )?$m$$n$$2^n$

Memang, mengatur pengemasan, partisi, dan penutup telah dipelajari dalam hal waktu berjalan algoritma yang tepat. Untuk menjawab pertanyaan terakhir Anda, Anda dapat menyelesaikan pengemasan tertimbang dalam waktu dengan pemrograman dinamis di semua himpunan bagian dari [ n ] . Selain itu, jika bobot bilangan bulat Anda dibatasi oleh M , Anda dapat menyelesaikannya dalam waktu O ( M 2 n ) , bahkan jika m sebesar 2 n , lihat$O(m2^n)$$[n]$$M$$O(M2^n)$$m$$2^n$

http://dx.doi.org/10.1137/070683933

BTW, Hasil parameterisasi yang Anda daftarkan untuk set bukan yang paling dikenal, lihat$3$

http://arxiv.org/abs/1007.1161

untuk algoritme canggih dan daftar hasil sebelumnya tentang masalah tersebut.

$O(2^{0.288n})$