现有一列随机的正整数,算他有2^n个吧,然后两两结合生成一个二叉树,节点是上一级两个数的和,合成的cost是上一级两个数的乘积。 而整个树的cost由总cost最高的那个branch决定,求用什么方法排列这一列数使生成的树cost最低。
例如,1,2,3,4这四个数
C=21+12=33
bisect(List, Left, Right) :- | |
append(Left, Right, List), | |
length(Left, LeftLength), | |
length(Right, RightLength), | |
LeftLength = RightLength. | |
element_cost(List, Cost) :- | |
bisect(List, Left, Right), | |
sum_list(Left, LeftSum), | |
sum_list(Right, RightSum), | |
Cost is (LeftSum * RightSum). | |
tree_cost([_], 0). | |
tree_cost(List, Cost) :- | |
bisect(List, Left, Right), | |
tree_cost(Left, LeftCost), | |
tree_cost(Right, RightCost), | |
max_list([LeftCost, RightCost], BiggerCost), | |
element_cost(List, ElementCost), | |
Cost is (ElementCost + BiggerCost). | |
all_cost(List, TargetList, Cost) :- | |
permutation(List, TargetList), | |
tree_cost(TargetList, Cost). | |
min_cost(List, Cost) :- | |
findall(TargetCost, all_cost(List, _, TargetCost), CostList), | |
min_list(CostList, Cost). | |
min_cost_with_list(List, MinList, Cost) :- | |
findall([TargetList, TargetCost], all_cost(List, TargetList, TargetCost), AllList), | |
maplist(last, AllList, CostList), | |
min_list(CostList, Cost), | |
member([MinList, Cost], AllList). |