Analisis algoritma PHP: Bagaimana untuk menggunakan algoritma pengaturcaraan dinamik untuk menyelesaikan masalah ransel 0-1?

Analisis algoritma PHP: Bagaimana menggunakan algoritma pengaturcaraan dinamik untuk menyelesaikan masalah ransel 0-1?

Pengenalan:
Pengaturcaraan dinamik ialah idea algoritma yang biasa digunakan untuk menyelesaikan masalah pengoptimuman. Dalam pembangunan program, masalah ransel 0-1 ialah senario aplikasi pengaturcaraan dinamik klasik. Artikel ini akan memperkenalkan cara menggunakan PHP untuk menulis algoritma pengaturcaraan dinamik untuk menyelesaikan masalah ransel 0-1 dan memberikan contoh kod khusus.

Apakah masalah ransel 0-1?
Masalah ransel 0-1 ialah masalah pengoptimuman gabungan klasik. Masalahnya ditetapkan seperti berikut: Terdapat beg galas dengan kapasiti C. Terdapat n item, setiap item mempunyai berat w[i] dan nilai v[i]. Ia dikehendaki memilih gabungan item untuk memaksimumkan jumlah nilai tanpa melebihi kapasiti beg galas.

Penyelesaian pengaturcaraan dinamik
Algoritma pengaturcaraan dinamik membahagikan masalah yang diberikan kepada satu siri sub-masalah dan menyimpan penyelesaian optimum bagi sub-masalah, dan akhirnya menyelesaikan penyelesaian optimum bagi keseluruhan masalah. Untuk masalah ransel 0-1, kita boleh menggunakan algoritma pengaturcaraan dinamik untuk menyelesaikannya.

Idea algoritma:

1. Buat dp tatasusunan dua dimensi, dpi mewakili nilai maksimum apabila hanya item i pertama dipertimbangkan dan kapasiti beg galas ialah j.
2. Mulakan tatasusunan dp, tetapkan semua elemen kepada 0.

3. Item traverse:

   • Untuk setiap item, jika beratnya kurang daripada atau sama dengan kapasiti beg galas j, anda perlu membandingkan nilai item semasa item dimasukkan dan apabila item tidak dimasukkan. , dan pilih penyelesaian yang lebih besar untuk mengemas kini tatasusunan dp.
   • Jika berat barang lebih besar daripada kapasiti beg galas j, anda hanya boleh memilih untuk tidak memasukkan barang tersebut, iaitu dpi = dpi-1.
4. Selepas kitaran tamat, dpn ialah nilai maksimum apabila kapasiti beg galas ialah C.

Contoh kod khusus:

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

// 示例输入
$C = 10; // 背包容量
$weight = array(2, 3, 4, 5); // 物品重量
$value = array(3, 4, 5, 6); // 物品价值
$n = count($weight); // 物品数量

// 输出最大价值
echo "背包容量为 " . $C . " 时的最大价值为：" . knapsack($C, $weight, $value, $n);

Analisis kod:

• fungsiknapsackmenerima empat parameter: kapasiti beg galas C, berat susunan berat item, nilai tatasusunan nilai item dan kuantiti item n.
• Buat tatasusunan dua dimensi $dp untuk menyimpan penyelesaian optimum kepada sub-masalah.
• Mulakan tatasusunan dp, tetapkan semua elemen kepada 0.
• Gelung item dan buat pertimbangan serta kemas kini berdasarkan persamaan peralihan keadaan pengaturcaraan dinamik.
• Selepas gelung tamat, dpn yang dikembalikan ialah nilai maksimum apabila kapasiti beg galas ialah C.

Kesimpulan:
Dengan menggunakan algoritma pengaturcaraan dinamik untuk menyelesaikan masalah knapsack 0-1, nilai maksimum yang boleh disimpan oleh ransel dapat diselesaikan dengan cekap. Dalam PHP, algoritma ini boleh dilaksanakan dengan menulis kod yang sesuai. Idea algoritma ini bukan sahaja boleh digunakan untuk masalah ransel 0-1, tetapi juga boleh digunakan untuk masalah pengoptimuman gabungan lain yang serupa.

Atas ialah kandungan terperinci Analisis algoritma PHP: Bagaimana untuk menggunakan algoritma pengaturcaraan dinamik untuk menyelesaikan masalah ransel 0-1?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!