Problema de mochila en palabras simples

Hace un par de años, enfrenté el llamado problema de la mochila en una de las entrevistas y rápidamente encontré una solución en Internet. Traté de entenderlo y ... no entendí nada. ¿Cómo cambió los nombres de las variables y quién no lo hace cuando encuentra una solución preparada para la tarea en casa? Lo envié y lo olvidé como una pesadilla. Recientemente, un amigo lanzó un problema similar sobre las monedas y esta vez rápidamente lo descubrí una vez, ya que me parecía una tarea abrumadora.

Me gustaría agradecer el libro Grokking Algorithms de Aditya Bhargava. Describe sin rodeos los conceptos básicos de los algoritmos en el lenguaje más simple. Entonces, si, como yo en la universidad, pensabas que los algoritmos nunca te serían útiles, porque FAANG no es para ti. Entonces los decepcionaré y los deleitaré, todos pueden llegar allí, si, por supuesto, se esfuerzan lo suficiente, pero lo decepcionaré con el hecho de que, por supuesto, debe esforzarse y dominar los algoritmos, y cuanto antes comience a hacerlo. esto, mejor.

En Habré, ya hay un artículo sobre este tema: Algoritmo para resolver el problema de la mochila (versión 2, revisada) / Habr (habr.com) . Pero, que me perdone el autor, en mi opinión es completamente incomprensible.

Y entonces, pongámonos manos a la obra. Primero, te diré todo lo que esté en mis dedos, y luego veremos la solución en nuestro C # favorito.

La tarea en sí es una de sus variaciones populares. El ladrón se dirigió a la joyería, tiene una mochila con un volumen de 4 unidades. En la tienda, vio tres cosas:

Su tarea es encajar de manera óptima estas cosas en una mochila para que pueda llevarse las joyas al máximo costo.

Hay varias formas de solucionar este problema. Uno de ellos es la enumeración de todas las opciones.

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

. , .

:

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

. , .

1: , 0.

2: , 0.

3: , 0.

4: , 4 4. , , , .

. , .

. :

1: . , , . .

2: 1. .

3: 1. .

4: , , , , . , !

,

1: , , , 1.

2: 1.

3: , , .

4: , , . 500 . 4500 4 .

.

? , , . , !

i, j.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

!