Bagaimanakah Kami Boleh Menentukan Item yang Disertakan dalam Penyelesaian Knapsack Optimum dengan Cekap?

Menentukan Elemen dalam Penyelesaian Knapsack Optimum

Algoritma Knapsack yang diberikan dengan cekap mengira nilai optimum untuk masalah pembungkusan tong sampah. Walau bagaimanapun, tugas di tangan adalah untuk mengenal pasti unsur-unsur yang membentuk penyelesaian optimum ini.

1. Menjejaki Pemilihan:

Selepas mengira nilai optimum dalam matriks dp, kita boleh menjejaki belakang untuk menentukan elemen yang dipilih.

dp_copy = dp;  // Copy the dp matrix for backtracking

int weight_idx = W;
int item_idx = n;

while (weight_idx > 0 && item_idx > 0):
    if dp_copy[weight_idx][item_idx] != dp_copy[weight_idx - items[item_idx - 1].getWeight()][item_idx - 1]:
        // Element 'item_idx' is included in the optimal solution
        weight_idx -= items[item_idx - 1].getWeight()
        item_idx -= 1

2. Tafsiran Kod Pseudo:

• Kami mengulang melalui matriks dp dalam susunan terbalik dari sel terakhir hingga yang pertama.
• Kami menyemak sama ada perbezaan antara sel semasa dan sel di atas dan di sebelah kiri dalam matriks sama dengan berat item yang sepadan.
• Jika ya, item yang dikaitkan dengan sel itu nilai disertakan dalam penyelesaian.
• Kami melaraskan indeks berat dan indeks item dengan sewajarnya untuk menjejak ke belakang lagi.

3. Kerumitan:

Pendekatan menjejak ke belakang ini memerlukan kerumitan masa O(W * n), dengan W ialah kapasiti beg dan n ialah bilangan item. Ia berulang melalui setiap sel dalam matriks sekali dan melakukan operasi carian masa tetap.

Atas ialah kandungan terperinci Bagaimanakah Kami Boleh Menentukan Item yang Disertakan dalam Penyelesaian Knapsack Optimum dengan Cekap?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!