Bagaimanakah Kami Boleh Mengenalpasti Item Khusus yang Disertakan dalam Penyelesaian Knapsack Optimum?

Menentukan Elemen dalam Penyelesaian Knapsack Optimum

Algoritma ransel, penyelesaian kepada masalah pembungkusan tong keras NP, mengira yang optimum nilai yang boleh dicapai daripada satu set item dengan kapasiti terhad. Walau bagaimanapun, ia sering membuatkan pengguna tertanya-tanya item tertentu yang menyumbang kepada penyelesaian optimum ini.

Untuk menangani isu ini, kami boleh mengubah suai algoritma ransel untuk menjejaki elemen yang dipilih semasa proses pengoptimuman. Ini menyediakan cara langsung untuk mengenal pasti item yang terdiri daripada penyelesaian optimum, dan bukannya bergantung semata-mata pada nilai penyelesaian.

Pendekatan:

1. Buat tambahan matriks dipilih, apabila dipilih[w][j] menunjukkan sama ada elemen pada indeks j-1 telah dipilih pada kapasiti w.
2. Mulakan matriks yang dipilih kepada 0.
3. Semasa algoritma ransel, semasa mengemas kini dp[w][j], tetapkan juga dipilih[w][j] kepada 1 jika item[ j-1] dipilih (dp[w][j] = dp[w - item[j-1].getWeight()][j-1] item[j-1].getWeight()) untuk menunjukkan bahawa elemen ini telah dipilih.
4. Selepas menentukan nilai optimum, jejak melalui matriks yang dipilih untuk mengenal pasti item khusus yang telah dipilih.

Pseudokod:

int Knapsack::knapsack(std::vector<Item>& items, int W)
{
    size_t n = items.size();
    std::vector<std::vector<int>> dp(W + 1, std::vector<int>(n + 1, 0));
    std::vector<std::vector<int>> selected(W + 1, std::vector<int>(n + 1, 0));
    for (size_t j = 1; j <= n; j++)
    {
        for (int w = 1; w <= W; w++)
        {
            if (items[j-1].getWeight() <= w)
            {
                dp[w][j] = std::max(dp[w][j-1], dp[w - items[j-1].getWeight()][j-1] + items[j-1].getWeight());
                selected[w][j] = (dp[w][j] != dp[w][j-1]);
            }
            else
            {
                dp[w][j] = dp[w][j - 1];
            }
        }
    }

    // Identify selected items
    std::vector<int> takenItems;
    int line = W;
    int i = n;
    while (i > 0) {
      if (selected[line][i]) {
        takenItems.push_back(items[i-1].getIndex()); // Index of item taken
        line -= items[i-1].getWeight();
      }
      i--;
    }

    return dp[W][n];
}

Algoritma ransel dipertingkat ini membolehkan pengenalpastian bukan sahaja nilai optimum tetapi juga elemen khusus yang menyumbang kepada penyelesaian optimum itu.

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