Knapsack problem in simple words

A couple of years ago, I faced the so-called backpack problem at one of the interviews, and quickly found a solution on the Internet. I tried to make it out and .... did not understand anything. How did he change the names of the variables, and who doesn't do that when he finds a ready-made solution for the home task? I sent it and forgot it like a bad dream. Recently, a friend threw off a similar problem about coins and this time I quickly figured out this once, as it seemed to me an overwhelming task.

I would like to acknowledge the book Grokking Algorithms by Aditya Bhargava. She straightforwardly describes the basics of algorithms in the simplest possible way. So if, like me at university, you thought that algorithms would never be useful to you, because FAANG is not for you. Then I will both disappoint and delight you, everyone can get there, if, of course, they make enough efforts, but I will disappoint you with the fact that of course you have to strain and master the algorithms, and the sooner you start doing this, the better.

On Habré, there is already one article on this topic: Algorithm for solving the knapsack problem (version 2, revised) / Habr (habr.com) . But, may the author forgive me, in my opinion it is completely incomprehensible.

And so, let's get down to business. First, I'll tell you everything on my fingers, and then we'll look at the solution in our favorite C #.

The task itself is one of its popular variations. The thief made his way to the jewelry store, he has a backpack with a volume of 4 units. In the store, he saw three things:

His task is to optimally fit these things in a backpack so that he would take away jewelry at the maximum cost.

There are several ways to solve this. One of them is enumeration of all options.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

!