Bagaimana untuk menggunakan backtracking untuk mencapai penyelesaian yang cekap kepada masalah ransel 0-1 dalam PHP?

Bagaimana untuk menggunakan backtracking untuk mencapai penyelesaian yang cekap kepada masalah ransel 0-1 dalam PHP?

Masalah ransel ialah masalah pengoptimuman gabungan klasik yang sering disebut dalam banyak kursus algoritma dan temu duga. Salah satu masalah knapsack yang biasa berlaku ialah masalah knapsack 0-1, yang juga merupakan salah satu masalah knapsack yang paling asas. Masalah ransel 0-1 diterangkan seperti berikut: diberikan satu set item, setiap item mempunyai berat dan nilai. Sekarang sudah ada beg galas berkapasiti C. Kita perlu memilih beberapa barang untuk dimasukkan ke dalam beg galas supaya jumlah berat barang tidak melebihi kapasiti beg galas dan jumlah nilai barang dimaksimumkan.

Kaedah backtracking ialah algoritma klasik untuk menyelesaikan masalah pengoptimuman gabungan Ia akhirnya menemui penyelesaian optimum dengan sentiasa mencuba ruang penyelesaian yang mungkin. Kaedah backtracking boleh memainkan peranan besar dalam mencapai penyelesaian yang cekap kepada masalah ransel 0-1. Berikut ialah contoh kod khusus menggunakan kaedah backtracking untuk melaksanakan masalah ransel 0-1 dalam PHP:

<?php

// 通过回溯法解决0-1背包问题

/**
 * @param int $maxValue 当前最大价值
 * @param int $curWeight 当前已选择物品的总重量
 * @param int $curValue 当前已选择物品的总价值
 * @param int $curIndex 当前已选择的物品索引
 * @param int $totalWeight 背包的总重量
 * @param int[] $weights 物品的重量数组
 * @param int[] $values 物品的价值数组
 * @return int 当前已选择物品的最大价值
 */
function knapsack($maxValue, $curWeight, $curValue, $curIndex, $totalWeight, $weights, $values)
{
    if ($curIndex == count($weights) || $curWeight == $totalWeight) {
        return $curValue;
    }
  
    $value1 = 0;
    if ($curWeight + $weights[$curIndex] <= $totalWeight) {
        // 选择当前物品
        $value1 = knapsack($maxValue, $curWeight + $weights[$curIndex], $curValue + $values[$curIndex], $curIndex + 1, $totalWeight, $weights, $values);
    }
  
    // 不选择当前物品
    $value2 = knapsack($maxValue, $curWeight, $curValue, $curIndex + 1, $totalWeight, $weights, $values);

    return max($value1, $value2);
}
  
$weights = [2, 3, 4, 5]; // 物品的重量数组
$values = [3, 4, 8, 9]; // 物品的价值数组
$totalWeight = 9;  // 背包的总重量

$maxValue = knapsack(0, 0, 0, 0, $totalWeight, $weights, $values);

echo "最大价值为：" . $maxValue;

?>

Kod di atas menggunakan rekursi untuk menyelesaikan masalah ransel 0-1. Fungsi knapsack menerima satu siri parameter, termasuk nilai maksimum semasa, jumlah berat dan jumlah nilai item yang dipilih pada masa ini, indeks item yang dipilih pada masa ini, jumlah berat beg galas dan susunan berat dan nilai item. Dalam badan fungsi, mula-mula tentukan sama ada semua item telah dipilih atau beg galas telah diisi Jika ya, jumlah nilai item yang dipilih pada masa ini dikembalikan. Kemudian cuba pilih item semasa atau tidak pilih item semasa, selesaikan secara rekursif untuk nilai maksimum dalam kedua-dua kes, dan kembalikan nilai yang lebih besar daripada kedua-duanya. Akhirnya, nilai output maksimum adalah penyelesaian kepada masalah.

Kerumitan masa algoritma ini adalah eksponen, jadi akan ada isu prestasi tertentu apabila menangani masalah berskala besar. Walau bagaimanapun, dalam aplikasi praktikal, teknologi hafalan boleh ditambah untuk menyimpan hasil yang dikira untuk mengelakkan pengiraan berulang dan meningkatkan kecekapan program.

Atas ialah kandungan terperinci Bagaimana untuk menggunakan backtracking untuk mencapai penyelesaian yang cekap kepada masalah ransel 0-1 dalam PHP?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!