So schreiben Sie einen Rucksackproblem-Algorithmus mit C#

So schreiben Sie einen Rucksackproblem-Algorithmus mit C#

Das Rucksackproblem (Rucksackproblem) ist ein klassisches kombinatorisches Optimierungsproblem, das einen Rucksack mit einer gegebenen Kapazität und einer Reihe von Artikeln beschreibt, wobei jeder Artikel seinen eigenen Wert hat und Gewicht. Ziel ist es, eine optimale Strategie zu finden, die den Gesamtwert der im Rucksack verpackten Gegenstände maximiert, ohne das Fassungsvermögen des Rucksacks zu überschreiten.

In C# kann das Rucksackproblem durch eine dynamische Programmiermethode gelöst werden. Die spezifische Implementierung ist wie folgt:

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

Im obigen Code haben wir eine statische Methode namens Knapsack definiert, die das Artikelgewicht-Array weights und das Artikelwert-Array values, Rucksackkapazität capacity und Anzahl der Artikel n verwendet. In der Methode wird ein zweidimensionales Array dp verwendet, um die Zustandsübergangstabelle dp[i, j] darzustellen, die den Rucksack unter den ersten i darstellt. code> Elemente. Der maximale Wert, der geladen werden kann, wenn die Kapazität <code>j ist. 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

Dann verwenden wir eine doppelstufige Schleife, um die Zustandsübergangstabelle zu füllen. Wenn i oder j 0 ist, bedeutet dies, dass keine Gegenstände vorhanden sind oder die Rucksackkapazität 0 beträgt. Zu diesem Zeitpunkt beträgt der maximale Wert, der in den Rucksack geladen werden kann, 0 . Wenn das Gewicht des Artikels i kleiner oder gleich der aktuellen Rucksackkapazität j ist, können Sie Artikel i laden oder dies tun Wenn Sie das Element >i nicht laden möchten, nehmen Sie den Maximalwert der beiden als Wert von dp[i, j]. Wenn das Gewicht des Artikels i größer ist als die Rucksackkapazität j, können Sie Artikel i nur nicht laden.

Schließlich definieren wir in der Main-Methode ein Beispiel-Artikelgewichtsarray weights, ein Artikelwertarray values und eine Rucksackkapazität capacity und rufen Sie dann die Methode <code>Knapsack auf, um den Maximalwert zu berechnen, der in den Rucksack geladen werden kann, und drucken Sie das Ergebnis aus. 🎜🎜Durch die obige C#-Code-Implementierung können wir das Rucksackproblem leicht lösen und die beste Verpackungslösung erhalten. Selbstverständlich kann der Algorithmus in praktischen Anwendungen auch entsprechend den eigenen Bedürfnissen erweitert und optimiert werden. 🎜

Das obige ist der detaillierte Inhalt vonSo schreiben Sie einen Rucksackproblem-Algorithmus mit C#. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!