Problem18 重みの合計が最大となる経路を求める

問題

以下の三角形の頂点から下まで移動するとき、その数値の合計の最大値は23になる。

      3
     7 4
    2 4 6
   8 5 9 3
この例では 3 + 7 + 4 + 9 = 23

以下の三角形を頂点から下まで移動するとき、その最大の合計値を求めよ。

                            75
                           95 64
                          17 47 82
                         18 35 87 10
                        20 04 82 47 65
                       19 01 23 75 03 34
                      88 02 77 73 07 63 67
                     99 65 04 28 06 16 70 92
                    41 41 26 56 83 40 80 70 33
                   41 48 72 33 47 32 37 16 94 29
                  53 71 44 65 25 43 91 52 97 51 14
                 70 11 33 28 77 73 17 78 39 68 17 57
                91 71 52 38 17 14 91 43 58 50 27 29 48
               63 66 04 68 89 53 67 30 73 16 69 87 40 31
              04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

注: ここではたかだか 16384 通りのルートしかないので、すべてのパターンを試すこともできる。
 * Problem 67 は同じ問題だが100行あるので、総当りでは解けない。もっと賢い方法が必要である。*/

ソース

using System;
using System.Collections.Generic;

class Program
{
    internal struct JyoutaiDef
    {
        internal int X;
        internal int Y;
        internal string Keiro;
        internal int SumVal;
    };

    static void Main()
    {
        //var Sankaku = new int[][] {new int[] {3},
        //                           new int[] {7,4},
        //                           new int[] {2,4,6},
        //                           new int[] {8,5,9,3}};
        var Sankaku = new int[][] {new int[] {75},
                                   new int[] {95,64},
                                   new int[] {17,47,82},
                                   new int[] {18,35,87,10},
                                   new int[] {20,04,82,47,65},
                                   new int[] {19,01,23,75,03,34},
                                   new int[] {88,02,77,73,07,63,67},
                                   new int[] {99,65,04,28,06,16,70,92},
                                   new int[] {41,41,26,56,83,40,80,70,33},
                                   new int[] {41,48,72,33,47,32,37,16,94,29},
                                   new int[] {53,71,44,65,25,43,91,52,97,51,14},
                                   new int[] {70,11,33,28,77,73,17,78,39,68,17,57},
                                   new int[] {91,71,52,38,17,14,91,43,58,50,27,29,48},
                                   new int[] {63,66,04,68,89,53,67,30,73,16,69,87,40,31},
                                   new int[] {04,62,98,27,23,09,70,98,73,93,38,53,60,04,23}};

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.X = WillPush.Y = 0;
        WillPush.Keiro = Sankaku[0][0].ToString();
        WillPush.SumVal = Sankaku[0][0];
        Stk.Push(WillPush);

        int KariMax = 0;

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            if (Popped.X == Sankaku.GetUpperBound(0)) {
                if (KariMax < Popped.SumVal) {
                    KariMax = Popped.SumVal;
                    Console.WriteLine("{0},SumVal={1}", Popped.Keiro, Popped.SumVal);
                }
                continue;
            }

            WillPush.X = Popped.X + 1;
            WillPush.Y = Popped.Y;
            WillPush.Keiro = Popped.Keiro + "," + Sankaku[WillPush.X][WillPush.Y];
            WillPush.SumVal = Popped.SumVal + Sankaku[WillPush.X][WillPush.Y];
            Stk.Push(WillPush);

            WillPush.X = Popped.X + 1;
            WillPush.Y = Popped.Y + 1;
            WillPush.Keiro = Popped.Keiro + "," + Sankaku[WillPush.X][WillPush.Y];
            WillPush.SumVal = Popped.SumVal + Sankaku[WillPush.X][WillPush.Y];
            Stk.Push(WillPush);
        }
    }
}

実行結果

75,64,82,10,65,34,67,92,33,29,14,57,48,31,23,SumVal=724
75,64,82,10,65,34,67,92,33,29,14,57,48,40,60,SumVal=770
75,64,82,10,65,34,67,92,33,29,14,57,29,87,60,SumVal=798
75,64,82,10,65,34,67,92,33,29,51,68,27,87,60,SumVal=844
75,64,82,10,65,34,67,92,33,94,51,17,29,87,60,SumVal=860
75,64,82,10,65,34,67,92,33,94,51,68,27,87,60,SumVal=909
75,64,82,10,65,34,67,92,33,94,97,68,27,87,60,SumVal=955
75,64,82,10,65,34,67,92,33,94,97,39,58,73,93,SumVal=976
75,64,82,10,65,34,67,92,70,94,97,68,27,87,60,SumVal=992
75,64,82,10,65,34,67,92,70,94,97,39,58,73,93,SumVal=1013
75,64,82,87,47,3,63,70,70,94,97,39,58,73,93,SumVal=1015
75,64,82,87,47,75,73,6,83,32,91,78,58,73,93,SumVal=1017
75,64,82,87,47,75,73,28,83,32,91,78,58,73,93,SumVal=1039
75,64,82,87,82,75,73,6,83,32,91,78,58,73,93,SumVal=1052
75,64,82,87,82,75,73,28,83,32,91,78,58,73,93,SumVal=1074

解説

深さ優先探索で全ての経路を網羅してます。