Apakah masalah 0-1 Knapsack di mana nilainya sama dengan bobot NP-complete?

9

Saya memiliki masalah yang saya duga adalah NP-complete. Sangat mudah untuk membuktikan bahwa itu adalah NP. Kereta pikiran saya saat ini berkisar menggunakan pengurangan dari ransel tetapi akan menghasilkan contoh 0-1-ransel dengan nilai setiap item sama dengan beratnya.

Apakah ini masih lengkap dengan NP? Atau apakah saya melewatkan sesuatu?

complexity-theory np-complete decision-problem packing Zeta Two
sumber
Ini sudah bertahun-tahun terlambat, tetapi bagaimanapun juga: Kata-kata Anda menunjukkan bahwa Anda mungkin mencoba mengurangi arah yang salah. Anda perlu mengurangi dari knapsack ke masalah Anda, artinya Anda harus mengizinkan instance Knapsack yang berubah-ubah (yang dapat menghasilkan instance dari masalah Anda yang memiliki beberapa struktur khusus) - tidak ada bagian dari prosedur ini yang akan "menghasilkan" Knapsack instance dengan beberapa spesial struktur. (OTOH, masuk akal untuk bertanya apakah beberapa kasus khusus Knapsack masih lengkap NP, karena mungkin lebih mudah untuk mengurangi dari.)
j_random_hacker
Iya. Yang saya maksud adalah bahwa saya mengurangi dari ransel tetapi secara khusus dari "0-1-ransel dengan nilai setiap item sama dengan beratnya". Jadi, hanya kata-kata saya yang sedikit aneh.
Zeta Two

Jawaban:

9

Ya, ini disebut masalah subset-sum dan NP-Hard.

Aryabhata
sumber
Terima kasih! Saya baru menyadari bahwa saya melakukan penemuan itu sebelumnya. Sayangnya saya juga menyadari bahwa pengurangan saya tidak bekerja sama sekali. Kembali ke papan gambar. :(
Zeta Two
@ ZetaTwo: Terima kasih kembali :-)
Aryabhata