Melaksanakan masalah ransel 0/1 dalam C/C++ menggunakan kaedah cawangan-dan-terikat

Ideanya adalah untuk menyedari hakikat bahawa kaedah tamak memberikan penyelesaian terbaik kepada masalah beg beg pecahan.

Untuk menyemak sama ada nod tertentu boleh memberikan kami penyelesaian yang lebih baik, kami mengira penyelesaian terbaik (mengikut nod) yang melaksanakan pendekatan tamak. Jika kaedah tamak itu sendiri mengira lebih banyak penyelesaian daripada penyelesaian terbaik setakat ini, maka kita tidak boleh mendapatkan penyelesaian yang lebih baik melalui nod.

Algoritma lengkap adalah seperti berikut -

• Susun semua item mengikut tertib menurun nilai per unit nisbah berat supaya had atas boleh dikira menggunakan kaedah tamak.

• Memulakan keuntungan maksimum, contohnya maxProfit = 0

• Buat baris gilir kosong Q.

• Keputusan nod maya mencipta pokok dan memasukkan atau beratur ke dalam Q. Keuntungan dan berat nod maya ialah 0.

• Lakukan operasi berikut apabila Q tidak kosong atau kosong.

  • Mencipta projek dalam Q. Biarkan item perahan ialah u.

  • Kira keuntungan nod peringkat seterusnya. Jika keuntungan lebih tinggi daripada maxProfit, ubah suai maxProfit.

  • Kira sempadan nod tahap seterusnya. Jika terikat lebih tinggi daripada maxProfit, tambahkan nod tahap seterusnya kepada Q.

  • Pertimbangkan situasi di mana nod peringkat seterusnya tidak dipertimbangkan atau dianggap sebagai sebahagian daripada penyelesaian dan tambahkan nod ke baris gilir di peringkat seterusnya tetapi berat dan keuntungan tidak mengendalikan atau mempertimbangkan nod peringkat seterusnya.

Ilustrasi diberikan di bawah -

Input

// First thing in every pair is treated as weight of item
// and second thing is treated as value of item
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10

Output

The maximum possible profit = 235

Atas ialah kandungan terperinci Melaksanakan masalah ransel 0/1 dalam C/C++ menggunakan kaedah cawangan-dan-terikat. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!