Comment écrire un algorithme de problème de sac à dos en utilisant C#

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

Ensuite, nous utilisons une boucle à double niveau pour remplir la table de transition d'état. Si 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!