👨‍🚒 🙌 ☁️ 簡単な言葉でナップサック問題 😝 👩‍💻 🎯

数年前、あるインタビューでいわゆるリュックサック問題に直面し、すぐにインターネットで解決策を見つけました。私はそれを作り出そうとしましたが、....何もわかりませんでした。彼は変数の名前をどのように変更したのでしょうか。また、自宅のタスクの既成の解決策を見つけたときに、誰がそれを変更しませんでしたか? 送ったのに、悪い夢のように忘れてしまいました。最近、友人がコインに関する同様の問題を投げかけましたが、今回はこれをすぐに見つけました。それは私にとって大変な作業に思えたからです。

Aditya Bhargava の著書Grokking Algorithms に感謝します。彼女はアルゴリズムの基本を最も単純な言語で率直に説明しています。ですから、もし大学の私のように、FAANG はあなたに向いていないので、アルゴリズムは自分にとって決して役に立たないと考えたのです。もちろん、彼らが十分な努力をすれば、誰もがそこに到達できますが、もちろん、アルゴリズムを緊張させて習得する必要があるという事実に私はあなたを失望させます.これは、より良いです。

：Habréでは、このトピックの1品すでにあるアルゴリズム/ Habr（habr.com）（改訂版2）ナップザック問題を解決するため。しかし、作者が許してくれますように、私の意見では、それは完全に理解できません。

それでは、本題に入りましょう。まず、私の指ですべてを説明し、次に、お気に入りの C # での解決策を見ていきます。

タスク自体は、その人気のあるバリエーションの 1 つです。泥棒は宝石店に向かいました。彼は 4 ユニット分のバックパックを持っています。店内で、彼は次の 3 つのことを発見しました。

彼の仕事は、これらのものをバックパックに最適に収めて、最大のコストでジュエリーを持ち去ることです。

これを解決するにはいくつかの方法があります。その 1 つは、すべてのオプションの列挙です。

, , 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.

最初のオプションは緑で強調表示され、2 番目のオプションは赤で強調表示されます。ご覧のとおり、赤い円のコストは緑の円のコストを上回っています。 — , .

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

簡単な言葉でナップサック問題

More articles: