C++ でナップザック問題アルゴリズムを使用する方法

C でナップサック問題アルゴリズムを使用する方法

ナップサック問題は、コンピューター アルゴリズムにおける古典的な問題の 1 つです。アイテムのトータル価値を最大限に高めるバックパック。この記事では、C で動的計画アルゴリズムを使用してナップザック問題を解決する方法と、具体的なコード例を詳しく紹介します。

まず、ナップザック問題の入力と出力を定義する必要があります。入力には、アイテムの重み配列 wt[]、アイテムの値配列 val[]、およびバックパックの容量 W が含まれます。アウトプットは、価値を最大化するためにバックパックに入れるアイテムを選択することです。定義は次のとおりです。

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]; // 返回最大价值
}

上記のコードでは、2 次元配列 dp[][] を使用して動的プログラミングの状態遷移テーブルを表します。ここで、dpi は最初の i 項目の選択を表します。 、バックパックの容量は j ケースの最大合計値です。特定のアルゴリズムは次のように実装されます。

1. 2 次元配列 dp[][] の最初の行と列を 0 に初期化します。これは、選択する項目がないこと、または最大値が存在しないことを意味します。容量が 0 の場合の合計値は 0;

2. 行 1 列 1 から開始して、各 dpi を計算します:

   • 現在のアイテムの重量 wt[i -1] はバックパックの容量 j 以下で、アイテムを入れるか入れないかを選択でき、両方の場合で最大の合計値を選択できます。
   • 現在のアイテムの重量が wt[i -1] はバックパックの容量 j より大きく、現在のアイテムを入れることはできません、合計値は前の状態、つまり dpi-1 に等しいです;
3. 最終的に戻りますdpn は、最初の n 個のアイテムが選択されており、バックパックの容量が最大合計値 W であることを示します。

以下は、ナップザック問題アルゴリズムを使用したサンプル コードです。

#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;
}

上記のコードを実行すると、出力結果の最大合計値は 220 になります。これは、ナップザック問題のアルゴリズムを使用した場合に、容量は50、アイテム1とアイテム3を選択することで獲得できる合計値の最大値となります。

上記の動的プログラミング手法に加えて、バックトラッキング アルゴリズムや貪欲アルゴリズムなどの他の手法を使用してナップザック問題を解決することもできます。上記は、C でナップザック問題アルゴリズムを使用する方法について詳しく説明したものです。お役に立てば幸いです。

以上がC++ でナップザック問題アルゴリズムを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。