Bagaimana untuk melaksanakan algoritma masalah knapsack menggunakan PHP

Cara melaksanakan algoritma masalah ransel dalam PHP

Masalah ransel ialah masalah pengoptimuman gabungan klasik. Dalam artikel ini, kami akan memperkenalkan cara menggunakan PHP untuk melaksanakan algoritma masalah ransel dan menyediakan contoh kod yang sepadan.

1. Penerangan tentang masalah beg beg

Masalah beg beg boleh digambarkan seperti berikut: diberi beg beg berkapasiti C dan barang N. Setiap item i mempunyai berat wi dan nilai vi. Ia dikehendaki memilih beberapa item daripada item N ini supaya jumlah beratnya tidak melebihi kapasiti beg galas C dan jumlah nilainya dimaksimumkan.

2. Algoritma Pengaturcaraan Dinamik

Pengaturcaraan dinamik ialah kaedah biasa untuk menyelesaikan masalah ransel. Idea asasnya adalah untuk membahagikan masalah kepada beberapa sub-masalah dan mengira penyelesaian optimum untuk setiap sub-masalah. Kemudian melalui pengulangan langkah demi langkah, penyelesaian optimum kepada masalah asal akhirnya diperolehi.

Berikut ialah contoh kod yang menggunakan algoritma pengaturcaraan dinamik untuk menyelesaikan masalah ransel:

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

$C = 10; // 背包容量
$weights = array(2, 3, 4, 5); // 物品重量
$values = array(3, 4, 5, 6); // 物品价值
$N = count($weights); // 物品数量

$result = knapsack($C, $weights, $values, $N);

echo "背包问题的最优解为：" . $result;

Kod di atas menggunakan tatasusunan dua dimensi$dp untuk merekodkan penyelesaian optimum bagi setiap sub-masalah. Di mana $dpi mewakili nilai maksimum memilih beberapa item antara item i pertama supaya jumlah beratnya tidak melebihi j. Formula rekursi ialah:

$dp[i][j] = max($values[i - 1] + $dp[i - 1][$j - $weights[i - 1]], $dp[i - 1][$j]);

Akhir sekali, kami mendapat penyelesaian optimum untuk masalah ransel dengan mengeluarkan $dpN.

3. Ringkasan

Artikel ini memperkenalkan cara menggunakan PHP untuk melaksanakan algoritma masalah knapsack Melalui pengaturcaraan dinamik, kita boleh menyelesaikan masalah knapsack dengan cekap. Saya harap artikel ini dapat memberikan sedikit bantuan kepada pembaca yang ingin mempelajari algoritma masalah knapsack.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma masalah knapsack menggunakan PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!