Comment écrire un algorithme de problème de sac à dos en utilisant C#
Le problème du sac à dos (Knapsack Problem) est un problème d'optimisation combinatoire classique, qui décrit un sac à dos avec une capacité donnée et une série d'éléments, chaque élément a sa propre valeur et poids. L’objectif est de trouver une stratégie optimale qui maximise la valeur totale des objets emballés dans le sac à dos sans dépasser la capacité du sac à dos.
En C#, le problème du sac à dos peut être résolu grâce à une méthode de programmation dynamique. L'implémentation spécifique est la suivante :
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); } } }
Dans le code ci-dessus, nous avons défini une méthode statique nommée Knapsack
, qui reçoit le tableau de poids d'élément weights
et le tableau de valeurs d'élément valeurs , capacité du sac à dos capacité
et nombre d'articles n
sont utilisés comme paramètres. Un tableau bidimensionnel dp
est utilisé dans la méthode pour représenter la table de transition d'état dp[i, j]
représente le sac à dos parmi les premiers icode> éléments La valeur maximale pouvant être chargée lorsque la capacité est <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
i
ou j
vaut 0, cela signifie qu'il n'y a aucun objet ou que la capacité du sac à dos est de 0. À l'heure actuelle, la valeur maximale pouvant être chargée dans le sac à dos est de 0. . Si le poids de l'article i
est inférieur ou égal à la capacité actuelle du sac à dos j
, vous pouvez choisir de charger l'article i
, ou vous pouvez choisissez de ne pas charger l'élément >i
, prenez la valeur maximale des deux comme valeur de dp[i, j]
. Si le poids de l'article i
est supérieur à la capacité du sac à dos j
, vous pouvez uniquement choisir de ne pas charger l'article i
. Enfin, dans la méthode Main
, nous définissons un exemple de tableau de poids d'article weights
, un tableau de valeurs d'article values
et la capacité du sac à dos capacity , puis appelez la méthode <code>Knapsack
pour calculer la valeur maximale pouvant être chargée dans le sac à dos et imprimez le résultat. 🎜🎜Grâce à l'implémentation du code C# ci-dessus, nous pouvons facilement résoudre le problème du sac à dos et obtenir la meilleure solution d'emballage. Bien entendu, dans les applications pratiques, l’algorithme peut également être étendu et optimisé en fonction de vos propres besoins. 🎜Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!