Bagaimanakah Saya Boleh Mendapatkan Item Khusus yang Disertakan dalam Penyelesaian Optimum Algoritma Knapsack?

Mendapatkan Elemen daripada Algoritma Knapsack

Algoritma Knapsack dengan cekap menentukan nilai optimum yang boleh dicapai daripada set item dengan kekangan. Walau bagaimanapun, ia hanya memberikan jumlah nilai tanpa menyatakan item mana yang menyumbang kepadanya.

Untuk mendapatkan elemen khusus yang disertakan dalam penyelesaian optimum, ikuti langkah-langkah ini dalam algoritma:

for (size_t j = 1; j <= n; j++)
{
    for ( int w = 1; w <= W; w++)
    {
        ...
        if (dp[w][j] != dp[w][j-1] && dp[w][j] == dp[w - items[j-1].getWeight()][j-1] + items[j-1].getWeight())
        {
            // Mark element 'j' as included in the solution
        }
    }
}

Ini step membandingkan nilai semasa dengan yang sebelumnya, mengenal pasti apabila item telah ditambahkan pada penyelesaian. Elemen yang dipilih membuat perbezaan antara nilai berturutan bersamaan dengan beratnya.

Sebagai alternatif, selepas algoritma telah dilaksanakan, anda boleh melintasi matriks secara terbalik untuk menentukan item yang dipilih:

int line = W;
int i = n;
while (i > 0):
    if (dp[line][i] - dp[line - weight(i)][i-1] == item[i].getValue()):
        // Item 'i' is in the solution
        i--;
        line -= weight(i);
    else:
        i--;

Pendekatan ini dengan cekap mendapatkan semula elemen yang menyumbang kepada penyelesaian optimum, memberikan pandangan yang lebih komprehensif tentang penyelesaian masalah.

Atas ialah kandungan terperinci Bagaimanakah Saya Boleh Mendapatkan Item Khusus yang Disertakan dalam Penyelesaian Optimum Algoritma Knapsack?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!