Hatena::Grouppython

Pythonで遊ぶよ

 | 

2009-04-17

最適ルート選択問題

06:29

                           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

最初の75からスタートして、右直下か左直下に1つずつ進むとき、通った数の合計が最大となるルートを求める。(最大値だけ答えればいい)

まず、総当たりによる回答がこれ。

#!/usr/bin/python

def parse_triangle():
    f = open('triangle.txt')
    rows = filter(lambda x: x != '' , f.read().split('\n'))
    tri = [map(int,r.split(' ')) for r in rows]
    f.close()
    return tri

def main():
    tri = parse_triangle()
    #for r in tri:
    #    print r
    routes = ['0']
    for row in tri[0:-1]:
        tmp = []
        for x in routes:
            tmp.append('%s%d' % (x,0))
            tmp.append('%s%d' % (x,1))
        routes = tmp

    best_route = (0,'')
    for x in routes:
        sum,n = 0,0
        for i,row in enumerate(tri):
            n += int(x[i])
            sum += row[n]
        if sum > best_route[0]: best_route = (sum,x)
   
    n,x = 0,best_route[1]
    for i,row in enumerate(tri):
        n += int(x[i])
        print row[n]
    print best_route[0]

if __name__ == '__main__':
    main()

結果。

% python triangle.py 
75
64
82
87
82
75
73
28
83
32
91
78
58
73
93
1074

総当たりじゃない回答も探してねと問題文にあるのだけど、それがなかなか思い付かなかった。

先に書かれてしまったけど、三角形の段数が n だとしたら、n-1 段目まで来たと仮定して、「最後の1段」を決める場合を考える。この場合は、次の2つの値のうち大きいほうを取ればいいので話は簡単。

その結果を元に三角形を n-1 段に縮退させる。次に n-2 段目を見て…と進んで1段目まで来れば答えが分かるということ。

#!/usr/bin/python

def parse_triangle():
    f = open('triangle.txt')
    rows = filter(lambda x: x != '' , f.read().split('\n'))
    tri = [map(int,r.split(' ')) for r in rows]
    f.close()
    return tri

def main():
    tri = parse_triangle()
    #for x in tri:
    #    print x
    dic = []
    while len(tri) != 1:
        last,before_last = tri.pop(),tri[-1]
        _dic = []
        for i,x in enumerate(before_last):
            index = i if last[i]>last[i+1] else i+1
            if len(dic) != 0:
                _dic.append([x] + dic[index])
            else:
                _dic.append([x])
            #_dic[i] = [x] + dic[index] if len(dic)!=0 else [x]
            before_last[i] = x + max( last[i], last[i+1] )
        dic[:] = _dic
    for x in dic[0]:
        print x
    print tri[0][0]

if __name__ == '__main__':
    main()
% python triangle_reform.py
75
64
82
87
82
75
73
28
83
32
91
78
58
73
1074

最初考えていた方法はこれとは違う方法で、惜しくも失敗だったのだけど、もったいないので明日書くことにする。

トラックバック - http://python.g.hatena.ne.jp/edvakf/20090417
 |