Masalah ransel dengan kata-kata sederhana

Beberapa tahun yang lalu, saya menghadapi apa yang disebut masalah ransel di salah satu wawancara, dan dengan cepat menemukan solusi di Internet. Saya mencoba untuk membuatnya keluar dan .... tidak mengerti apa-apa. Bagaimana dia mengubah nama variabel, dan siapa yang tidak melakukannya ketika dia menemukan solusi siap pakai untuk tugas rumah? Saya mengirimnya dan melupakannya seperti mimpi buruk. Baru-baru ini, seorang teman melemparkan masalah yang sama tentang koin dan kali ini saya dengan cepat menemukan ini sekali, karena bagi saya itu adalah tugas yang berat.

Saya ingin mengucapkan terima kasih kepada buku Algoritma Grokking oleh Aditya Bhargava. Dia dengan lugas menjelaskan dasar-dasar algoritma dalam bahasa yang paling sederhana. Jadi jika, seperti saya di universitas, Anda berpikir bahwa algoritme tidak akan pernah berguna bagi Anda, karena FAANG bukan untuk Anda. Maka saya akan mengecewakan dan menyenangkan Anda, semua orang bisa sampai di sana, jika, tentu saja, mereka melakukan upaya yang cukup, tetapi saya akan mengecewakan Anda dengan fakta bahwa tentu saja Anda harus berusaha keras dan menguasai algoritma, dan semakin cepat Anda mulai melakukannya ini, lebih baik.

Di Habré, sudah ada satu artikel tentang topik ini: Algoritma untuk memecahkan masalah ransel (versi 2, direvisi) / Habr (habr.com) . Tapi, semoga penulis memaafkan saya, menurut saya itu sama sekali tidak bisa dipahami.

Jadi, mari kita mulai bisnis. Pertama, saya akan memberi tahu Anda semua yang ada di jari saya, dan kemudian kita akan melihat solusinya di C # favorit kami.

Tugas itu sendiri adalah salah satu variasi populernya. Pencuri berjalan ke toko perhiasan, ia memiliki tas ransel dengan volume 4 unit. Di toko, dia melihat tiga hal:

Tugasnya adalah memasukkan barang-barang ini secara optimal ke dalam ransel sehingga dia bisa mengambil perhiasan dengan biaya maksimum.

Ada beberapa cara untuk menyelesaikan ini. Salah satunya adalah enumerasi semua opsi.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

!