🚹 🎴 😟 Problème de sac à dos en mots simples 😿 🔎 ⏭️

Il y a quelques années, j'ai été confronté au problème du sac à dos lors de l'un des entretiens et j'ai rapidement trouvé une solution sur Internet. J'ai essayé de comprendre et .... n'ai rien compris. Comment a-t-il changé les noms des variables, et qui ne le fait pas lorsqu'il trouve une solution toute faite pour la tâche domestique ? Je l'ai envoyé et je l'ai oublié comme un mauvais rêve. Récemment, un ami s'est posé un problème similaire à propos des pièces de monnaie et cette fois, j'ai rapidement compris cela une fois, car cela me semblait une tâche écrasante.

Je tiens à remercier le livre Grokking Algorithms d'Aditya Bhargava. Elle décrit simplement les bases des algorithmes dans le langage le plus simple. Alors si, comme moi à l'université, vous pensiez que les algorithmes ne vous seraient jamais utiles, car FAANG n'est pas pour vous. Alors je vais à la fois vous décevoir et vous ravir, tout le monde peut y arriver, si, bien sûr, ils font assez d'efforts, mais je vais vous décevoir par le fait que bien sûr vous devez forcer et maîtriser les algorithmes, et plus tôt vous commencez à faire ça, mieux c'est.

Sur Habré, il existe déjà un article sur ce sujet : Algorithme pour résoudre le problème du sac à dos (version 2, révisée) / Habr (habr.com) . Mais, que l'auteur me pardonne, à mon avis c'est complètement incompréhensible.

Et donc, passons aux choses sérieuses. Tout d'abord, je vais tout vous dire sur mes doigts, puis on va regarder la solution dans notre C# préféré.

La tâche elle-même est l'une de ses variantes populaires. Le voleur s'est dirigé vers la bijouterie, il a un sac à dos d'un volume de 4 unités. Dans le magasin, il a vu trois choses :

Sa tâche est de ranger de manière optimale ces choses dans un sac à dos afin qu'il puisse emporter les bijoux au coût maximum.

Il existe plusieurs façons de résoudre ce problème. L'un d'eux est l'énumération de toutes les options.

, , 3 8. 2ⁿ n - , 4, 16 . - Codility Timeout Exceeded. - .

. , .

	1	2	3	4
/ 4000 / 4
/ 2500 / 1
/ 2000 / 3

. , . 1, , , 1. , 1, 2, 3 4. ?)

	1	2	3	4
/ 4000 / 4	0	0	0	4000

. , .

1: , 0.

2: , 0.

3: , 0.

4: , 4 4. , , , .

. , .

	1	2	3	4
/ 4000 / 4	0	0	0	4000
/ 2500 / 1	2500	2500	2500	4000

. :

1: . , , . .

2: 1. .

3: 1. .

4: , , , , . , !

	1	2	3	4
/ 4000 / 4	0	0	0	4000
/ 2500 / 1	2500	2500	2500	4000
/ 2000 / 3	2500	2500	2500	4500

1: , , , 1.

2: 1.

3: , , .

4: , , . 500 . 4500 4 .

? , , . , !

i, j.

La première option est surlignée en vert, la seconde est surlignée en rouge. Comme vous pouvez le voir, le coût dans le cercle rouge l'emporte sur le coût dans le vert. — , .

C#:

public static int[] weights = { 4, 1, 3 };
public static int[] values = { 4000, 2500, 2000 };

public static int CountMax(int[] weights, int[] values, int maxCapacity)
{
    //        
    //    
    int[,] arr = new int[weights.Length + 1, maxCapacity + 1];

    //   
    for (int i = 0; i <= weights.Length; i++)
    {
        //   
        for (int j = 0; j <= maxCapacity; j++)
        {
            //   
            if (i == 0 || j == 0)
            {
                arr[i, j] = 0;
            }
            else
            {   
                //      
                //        
                //  .      
                if (weights[i - 1] > j)
                {
                    arr[i, j] = arr[i - 1, j];
                }
                else
                {
                    //  .    
                    var prev = arr[i - 1, j];
                    //  :  
                    //  :   -   
                    var byFormula = values[i - 1] + arr[i - 1, j - weights[i - 1]];
                    arr[i, j] = Math.Max(prev, byFormula);
                }
            }
        }
    }

    //    
    return arr[weights.Length, maxCapacity];
}

Problème de sac à dos en mots simples

More articles: