Problem 18 「最大経路の和 その1」 †
以下の三角形の頂点から下まで移動するとき, その数値の和の最大値は23になる.
3
7 4
2 4 6
8 5 9 3
この例では 3 + 7 + 4 + 9 = 23.
以下の三角形を頂点から下まで移動するとき, その最大の和を求めよ.
詳細はリンク先参照のこと。
解法
一段ずつの動的計画法で片が付きます。
max(A,B,A):-A>B,!.
max(_,B,B):-!.
calcCol([D],[X,Y],AddDX,[AddDY]):-
!,
write([X,Y,D]),
AddDY is D+Y,
AddDX is D+X.
calcCol([D|DP],[X,Y|Row],AddDX,[CommitNum|NextDP]):-
calcCol(DP,[Y|Row],ReDX,NextDP),
AddDY is D+Y,
max(AddDY,ReDX,CommitNum),
AddDX is D+X.
moveRow(Last,[],Last):-
!.
moveRow(DP,[Row|Rows],Result):-
calcCol(DP,Row,ReDX,NextDP),
moveRow([ReDX|NextDP],Rows,Result).
search_max([X],X):-!.
search_max([X|Xs],Result):-search_max(Xs,Re),max(X,Re,Result).
main18:-
X=[[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]],
[Seed|Rest]=X,
moveRow(Seed,Rest,LastDP),
search_max(LastDP,Ans),
write(Ans).
最終更新：2014年02月13日 16:23
