Bagaimana untuk menulis algoritma masalah ransel menggunakan C#

Cara menggunakan C# untuk menulis algoritma masalah ransel

Masalah ransel (Masalah Knapsack) ialah masalah pengoptimuman gabungan klasik, yang menerangkan masalah pengoptimuman kombinatorial yang diberikan Beg galas dengan kapasiti tetap dan koleksi item, setiap satu dengan nilai dan beratnya sendiri. Matlamatnya adalah untuk mencari strategi optimum yang memaksimumkan jumlah nilai item yang dibungkus ke dalam beg galas tanpa melebihi kapasiti beg galas.

Dalam C#, masalah ransel boleh diselesaikan melalui kaedah pengaturcaraan dinamik. Pelaksanaan khusus adalah seperti berikut:

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

Dalam kod di atas, kami mentakrifkan kaedah statik bernama Knapsack, yang menerima tatasusunan berat item weights , item Tatasusunan nilai nilai, kapasiti beg galas kapasiti dan bilangan item n digunakan sebagai parameter. Tatasusunan dua dimensi dp digunakan dalam kaedah untuk mewakili jadual peralihan keadaan dp[i, j] mewakili beg galas antara i yang pertama. kod> item nilai maksimum yang boleh dimuatkan apabila kapasiti adalah <code>j. Knapsack的静态方法，它接收物品重量数组weights、物品价值数组values、背包容量capacity和物品个数n作为参数。方法中使用一个二维数组dp来表示状态转移表，dp[i, j]表示在前i个物品中，背包容量为j时能装入的最大价值。

然后，我们使用双层循环来填充状态转移表。如果i或j为0时，表示没有物品或背包容量为0，此时背包能装入的最大价值为0。如果物品i的重量小于等于当前背包容量j，则可以选择装入物品i，也可以选择不装入物品i，取二者中最大的值作为dp[i, j]的值。如果物品i的重量大于背包容量j，则只能选择不装入物品i。

最后，在Main方法中我们定义了一个示例物品重量数组weights、物品价值数组values和背包容量capacity，然后调用Knapsack

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