C# を使用してナップザック問題アルゴリズムを作成する方法

C# を使用してナップサック問題アルゴリズムを作成する方法

ナップサック問題 (ナップサック問題) は、指定された容量のナップサックを記述する古典的な組み合わせ最適化問題です。それぞれが独自の価値と重みを持つアイテムのコレクション。目標は、バックパックの容量を超えずに、バックパックに詰めたアイテムの合計価値を最大化する最適な戦略を見つけることです。

C# では、動的プログラミングによってナップザック問題を解決できます。具体的な実装は次のとおりです。

using System;

namespace KnapsackProblem
{
    class Program
    {
        static int Knapsack(int[] weights, int[] values, int capacity, int n)
        {
            int[,] dp = new int[n + 1, capacity + 1];

            for (int i = 0; i <= n; i++)
            {
                for (int j = 0; j <= capacity; j++)
                {
                    if (i == 0 || j == 0)
                        dp[i, j] = 0;
                    else if (weights[i - 1] <= j)
                        dp[i, j] = Math.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, capacity];
        }

        static void Main(string[] args)
        {
            int[] weights = { 5, 3, 4, 2 };
            int[] values = { 60, 50, 70, 30 };
            int capacity = 8;
            int n = weights.Length;

            int maxValue = Knapsack(weights, values, capacity, n);
            Console.WriteLine("背包能装入的最大价值为：" + maxValue);
        }
    }
}

上記のコードでは、アイテムの重み配列 weights とアイテムの値を受け取る Knapsack という名前の静的メソッドを定義します。 arrayvalues、バックパック容量capacity、アイテム数nがパラメータとして使用されます。このメソッドでは、状態遷移表を表すために 2 次元配列 dp が使用されています。dp[i, j] は、最初の i 項目のうち、バックパックの容量は j で積載可能な最大値です。

次に、2 レベルのループを使用して状態遷移テーブルにデータを入力します。 i または j が 0 の場合は、アイテムがないか、バックパックの容量が 0 であることを意味します。このとき、バックパックに積める最大値は 0 です。アイテム i の重量が現在のバックパック容量 j 以下の場合、アイテム i を積むか、積まないかを選択できます。 item i、2 つの最大値を dp[i, j] の値として取得します。アイテム i の重量がバックパックの容量 j より大きい場合、アイテム i を積まないことを選択することしかできません。

最後に、Main メソッドで、サンプルのアイテム重量配列 weights、アイテム値配列 values、およびバックパック容量 容量を定義します。 を呼び出し、Knapsack メソッドを呼び出してバックパックに積み込める最大値を計算し、結果を出力します。

上記の C# コード実装を通じて、バックパックの問題を簡単に解決し、最適なパッケージング ソリューションを得ることができます。もちろん、実際のアプリケーションでは、独自のニーズに応じてアルゴリズムを拡張および最適化することもできます。

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