Bagaimana untuk menyelesaikan masalah knapsack dalam PHP menggunakan algoritma pengaturcaraan dinamik dan mendapatkan penyelesaian yang optimum?

Bagaimana untuk menggunakan algoritma pengaturcaraan dinamik untuk menyelesaikan masalah ransel dalam PHP dan mendapatkan penyelesaian yang optimum?

Masalah ransel adalah salah satu masalah pengoptimuman gabungan klasik dalam sains komputer. Memandangkan set barang dan kapasiti beg beg, cara memilih barang untuk dimasukkan ke dalam beg beg supaya dapat memaksimumkan jumlah nilai barang dalam beg beg adalah teras kepada masalah beg beg yang perlu diselesaikan.

Pengaturcaraan dinamik adalah salah satu kaedah biasa untuk menyelesaikan masalah ransel. Ia membahagikan masalah kepada sub-masalah dan menyimpan penyelesaian sub-masalah untuk akhirnya mendapatkan penyelesaian yang optimum. Di bawah ini kami akan menerangkan secara terperinci cara menggunakan algoritma pengaturcaraan dinamik untuk menyelesaikan masalah knapsack dalam PHP.

Pertama, kita perlu mentakrifkan input dan output masalah ransel:

Input:

• Susunan berat item $berat, $berat[$i] mewakili berat item $i-th
• Tatasusunan nilai item $values ​​, $values[$i] mewakili nilai item $i-th
• Kapasiti beg galas $capacity, mewakili kapasiti maksimum beg galas

Output:

• jumlah nilai maksimum item dalam beg galas

Seterusnya, kami Tatasusunan dua dimensi $dp perlu ditakrifkan untuk menyelamatkan penyelesaian kepada sub-masalah. $dp[$i][$j] mewakili jumlah nilai maksimum item $i pertama apabila kapasiti beg galas ialah $j.

Aliran algoritma adalah seperti berikut:

1. Mulakan tatasusunan $dp dan tetapkan semua elemen kepada 0.

2. Gelung luar melintasi indeks item, dari $i = 1 hingga $i = count($weights) - 1:

   • Gelung dalam merentasi kapasiti beg galas, dari $j = 0 hingga $j = $ kapasiti:

     • Jika berat item semasa $weights[$i] lebih besar daripada kapasiti beg galas $j, maka $dp[$i][$j] = $dp[$i - 1][$j], iaitu, Item semasa tidak boleh diletakkan di dalam beg galas, dan jumlah nilai maksimum adalah sama dengan $i - 1 item pertama.
     • Jika tidak, item semasa boleh dimasukkan ke dalam beg galas, dan nilai yang dijana $values[$i] ditambah dengan jumlah nilai maksimum sebelum meletakkan item $dp[$i - 1][$j - $weights[$ i ]], berbanding dengan nilai semasa, ambil nilai yang lebih besar sebagai $dp[$i][$j].
3. Mengembalikan $dp[count($weights) - 1][$capacity], iaitu jumlah nilai maksimum item kiraan pertama($weights) apabila kapasiti beg galas ialah $capacity.

Berikut ialah algoritma pengaturcaraan dinamik untuk melaksanakan masalah knapsack menggunakan kod PHP:

function knapsack($weights, $values, $capacity) {
    $dp = [];
    for ($i = 0; $i < count($weights); $i++) {
        $dp[$i] = [];
        for ($j = 0; $j <= $capacity; $j++) {
            $dp[$i][$j] = 0;
        }
    }
    
    for ($i = 1; $i < count($weights); $i++) {
        for ($j = 0; $j <= $capacity; $j++) {
            if ($weights[$i] > $j) {
                $dp[$i][$j] = $dp[$i - 1][$j];
            } else {
                $dp[$i][$j] = max($dp[$i - 1][$j], $values[$i] + $dp[$i - 1][$j - $weights[$i]]);
            }
        }
    }
    
    return $dp[count($weights) - 1][$capacity];
}

Menggunakan kod di atas, kita boleh menyelesaikan masalah knapsack dengan memanggil fungsi knapsack($weights, $values, $capacity) dan mendapatkan penyelesaian yang optimum.

Semoga artikel ini dapat membantu anda memahami cara menggunakan algoritma pengaturcaraan dinamik untuk menyelesaikan masalah ransel dalam PHP dan mendapatkan penyelesaian yang optimum.

Atas ialah kandungan terperinci Bagaimana untuk menyelesaikan masalah knapsack dalam PHP menggunakan algoritma pengaturcaraan dinamik dan mendapatkan penyelesaian yang optimum?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!