Problema da mochila em palavras simples

Há alguns anos, enfrentei o chamado problema da mochila em uma das entrevistas e rapidamente encontrei uma solução na Internet. Tentei decifrar e ... não entendi nada. Como ele mudou os nomes das variáveis, e quem não faz isso quando encontra uma solução pronta para a tarefa doméstica? Enviei e esqueci como um pesadelo. Recentemente, um amigo lançou um problema semelhante sobre moedas e desta vez eu rapidamente descobri isso uma vez, pois me pareceu uma tarefa opressora.

Eu gostaria de agradecer o livro Grokking Algorithms de Aditya Bhargava. Ela descreve diretamente os fundamentos dos algoritmos na linguagem mais simples. Então se, como eu na universidade, você pensou que algoritmos nunca seriam úteis para você, porque FAANG não é para você. Então eu vou decepcionar e encantar você, todos podem chegar lá, se, é claro, eles fizerem o suficiente, mas eu vou decepcioná-lo com o fato de que é claro que você tem que forçar e dominar os algoritmos, e quanto mais cedo você começar a fazer isso, melhor.

Sobre o Habré, já existe um artigo sobre o assunto: Algoritmo para solução do problema da mochila (versão 2, revisada) / Habr (habr.com) . Mas, que o autor me perdoe, em minha opinião é completamente incompreensível.

E então, vamos ao que interessa. Primeiro, vou lhe contar tudo em meus dedos e, em seguida, veremos a solução em nosso C # favorito.

A tarefa em si é uma de suas variações populares. O ladrão dirigiu-se à joalheria, trazendo consigo uma mochila com volume de 4 unidades. Na loja, ele viu três coisas:

Sua tarefa é encaixar perfeitamente essas coisas em uma mochila, de modo que ele leve as joias com o custo máximo.

Existem várias maneiras de resolver isso. Um deles é a enumeração de todas as opções.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

!