Bagaimana untuk menggunakan algoritma masalah knapsack dalam C++

Cara menggunakan algoritma masalah ransel dalam C++

Masalah ransel adalah salah satu masalah klasik dalam algoritma komputer Ia melibatkan cara memilih beberapa item untuk dimasukkan ke dalam beg beg di bawah kapasiti ransel yang diberikan, supaya jumlah keseluruhannya. nilai item memaksimumkan. Artikel ini akan memperkenalkan secara terperinci cara menggunakan algoritma pengaturcaraan dinamik dalam C++ untuk menyelesaikan masalah ransel, dan memberikan contoh kod khusus.

Pertama, kita perlu menentukan input dan output masalah ransel. Input termasuk tatasusunan berat wt[] item, tatasusunan nilai val[] item dan kapasiti W beg galas. Output memilih item yang hendak dimasukkan ke dalam beg galas untuk memaksimumkan nilai. Ia ditakrifkan seperti berikut:

int knapSack(int W, int wt[], int val[], int n) {
   // 动态规划表格
   int dp[n+1][W+1];
  
   // 填充动态规划表格
   for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= W; j++) {
         if (i == 0 || j == 0)
            dp[i][j] = 0; // 边界条件
         else if (wt[i - 1] <= j)
            dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j]);
         else
            dp[i][j] = dp[i - 1][j];
      }
   }
  
   return dp[n][W]; // 返回最大价值
}

Dalam kod di atas, kami menggunakan dp tatasusunan dua dimensi[][] untuk mewakili jadual peralihan keadaan pengaturcaraan dinamik, dengan dpi mewakili pemilihan item i pertama dan kapasiti beg galas. ialah j Jumlah nilai maksimum. Algoritma khusus dilaksanakan seperti berikut:

1. Memulakan baris dan lajur pertama tatasusunan dua dimensi dp[][] kepada 0, menunjukkan bahawa tiada item untuk dipilih atau jumlah nilai maksimum apabila kapasiti ialah 0 ialah 0;

2. Daripada Bermula dari baris 1 dan lajur 1, hitung setiap dpi:

   • Jika berat item semasa wt[i-1] kurang daripada atau sama dengan kapasiti beg galas j, anda boleh memilih untuk masukkan item ke dalam atau tidak untuk memasukkan item. Pilih jumlah nilai terbesar dalam situasi
   • Jika berat item semasa wt[i-1] lebih besar daripada kapasiti beg galas j, item semasa tidak boleh diletakkan; dalam, dan jumlah nilai adalah sama dengan keadaan sebelumnya, iaitu, dpi-1;
Berikut adalah contoh kod menggunakan algoritma masalah ransel:

3. #include 
   using namespace std;
   
   int knapSack(int W, int wt[], int val[], int n) {
      // 动态规划表格
      int dp[n+1][W+1];
     
      // 填充动态规划表格
      for (int i = 0; i <= n; i++) {
         for (int j = 0; j <= W; j++) {
            if (i == 0 || j == 0)
               dp[i][j] = 0; // 边界条件
            else if (wt[i - 1] <= j)
               dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j]);
            else
               dp[i][j] = dp[i - 1][j];
         }
      }
     
      return dp[n][W]; // 返回最大价值
   }
   
   int main() {
      int val[] = {60, 100, 120};
      int wt[] = {10, 20, 30};
      int W = 50;
      int n = sizeof(val) / sizeof(val[0]);
      cout << "最大总价值为：" << knapSack(W, wt, val, n) << endl;
      return 0;
   }

Jalankan kod di atas dan jumlah nilai maksimum hasil output ialah 220, bermakna apabila kapasiti beg galas ialah 50, nilai maksimum yang boleh diperoleh dengan memilih item 1 dan 3 jumlah nilai.

Selain kaedah pengaturcaraan dinamik di atas, masalah knapsack juga boleh diselesaikan menggunakan kaedah lain seperti algoritma backtracking dan tamak. Di atas adalah pengenalan terperinci tentang cara kami menggunakan algoritma masalah knapsack dalam C++ saya harap ia akan membantu anda.

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