※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。



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