トップページに戻る    次のC++のサンプルへ    前のC++のサンプルへ

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行あるので、総当りでは解けない。もっと賢い方法が必要である。*/

ソース

#include <iostream>
#include <Windows.h>
#include <vector>
#include <stack>

using namespace std;

struct defineKeiro
{
    int X;
    int Y;
    string Keiro;
    int SumVal;
};

char wkStr[256];

void main()
{
    //int wkArr01[]= {3};
    //int wkArr02[]= {7,4};
    //int wkArr03[]= {2,4,6};
    //int wkArr04[]= {8,5,9,3};
    //vector<int> Sankaku[]={
    //    vector<int>(wkArr01,wkArr01+sizeof(wkArr01)/sizeof(int)),
    //    vector<int>(wkArr02,wkArr02+sizeof(wkArr02)/sizeof(int)),
    //    vector<int>(wkArr03,wkArr03+sizeof(wkArr03)/sizeof(int)),
    //    vector<int>(wkArr04,wkArr04+sizeof(wkArr04)/sizeof(int))};
    int wkArr01[]= {75};
    int wkArr02[]= {95,64};
    int wkArr03[]= {17,47,82};
    int wkArr04[]= {18,35,87,10};
    int wkArr05[]= {20, 4,82,47,65};
    int wkArr06[]= {19, 1,23,75, 3,34};
    int wkArr07[]= {88, 2,77,73, 7,63,67};
    int wkArr08[]= {99,65, 4,28, 6,16,70,92};
    int wkArr09[]= {41,41,26,56,83,40,80,70,33};
    int wkArr10[]= {41,48,72,33,47,32,37,16,94,29};
    int wkArr11[]= {53,71,44,65,25,43,91,52,97,51,14};
    int wkArr12[]= {70,11,33,28,77,73,17,78,39,68,17,57};
    int wkArr13[]= {91,71,52,38,17,14,91,43,58,50,27,29,48};
    int wkArr14[]= {63,66, 4,68,89,53,67,30,73,16,69,87,40,31};
    int wkArr15[]= {04,62,98,27,23, 9,70,98,73,93,38,53,60, 4,23};
    vector<int> Sankaku[]={
        vector<int>(wkArr01,wkArr01+sizeof(wkArr01)/sizeof(int)),
        vector<int>(wkArr02,wkArr02+sizeof(wkArr02)/sizeof(int)),
        vector<int>(wkArr03,wkArr03+sizeof(wkArr03)/sizeof(int)),
        vector<int>(wkArr04,wkArr04+sizeof(wkArr04)/sizeof(int)),
        vector<int>(wkArr05,wkArr05+sizeof(wkArr05)/sizeof(int)),
        vector<int>(wkArr06,wkArr06+sizeof(wkArr06)/sizeof(int)),
        vector<int>(wkArr07,wkArr07+sizeof(wkArr07)/sizeof(int)),
        vector<int>(wkArr08,wkArr08+sizeof(wkArr08)/sizeof(int)),
        vector<int>(wkArr09,wkArr09+sizeof(wkArr09)/sizeof(int)),
        vector<int>(wkArr10,wkArr10+sizeof(wkArr10)/sizeof(int)),
        vector<int>(wkArr11,wkArr11+sizeof(wkArr11)/sizeof(int)),
        vector<int>(wkArr12,wkArr12+sizeof(wkArr12)/sizeof(int)),
        vector<int>(wkArr13,wkArr13+sizeof(wkArr13)/sizeof(int)),
        vector<int>(wkArr14,wkArr14+sizeof(wkArr14)/sizeof(int)),
        vector<int>(wkArr15,wkArr15+sizeof(wkArr15)/sizeof(int))
    };

    stack<defineKeiro> stk;
    defineKeiro WillPush;
    WillPush.X = WillPush.Y = 0;
    wsprintf(wkStr,"%d",Sankaku[0].at(0));
    WillPush.Keiro = wkStr;
    WillPush.SumVal = Sankaku[0].at(0);
    stk.push(WillPush);

    int kariMax = 0;

    while (stk.empty() == false){
        defineKeiro Popped = stk.top();stk.pop();

        if(Popped.X == sizeof(Sankaku)/sizeof(Sankaku[0])-1){
            if (kariMax < Popped.SumVal) {
                kariMax = Popped.SumVal;
                cout << Popped.Keiro.c_str() << ",SumVal=" << Popped.SumVal << endl;
            }
            continue;
        }

        WillPush.X = Popped.X + 1;
        WillPush.Y = Popped.Y;
        WillPush.Keiro = Popped.Keiro;
        WillPush.Keiro += ",";
        wsprintf(wkStr,"%d",Sankaku[WillPush.X].at(WillPush.Y));
        WillPush.Keiro += wkStr;
        WillPush.SumVal = Popped.SumVal + Sankaku[WillPush.X].at(WillPush.Y);
        stk.push(WillPush);

        WillPush.X = Popped.X + 1;
        WillPush.Y = Popped.Y + 1;
        WillPush.Keiro = Popped.Keiro;
        WillPush.Keiro += ",";
        wsprintf(wkStr,"%d",Sankaku[WillPush.X].at(WillPush.Y));
        WillPush.Keiro += wkStr;
        WillPush.SumVal = Popped.SumVal + Sankaku[WillPush.X].at(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

解説

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