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
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!