现有一列随机的正整数，算他有2^n个吧，然后两两结合生成一个二叉树，节点是上一级两个数的和，合成的cost是上一级两个数的乘积。 而整个树的cost由总cost最高的那个branch决定，求用什么方法排列这一列数使生成的树cost最低。

problem.markdown

现有一列随机的正整数，算他有2^n个吧，然后两两结合生成一个二叉树，节点是上一级两个数的和，合成的cost是上一级两个数的乘积。 而整个树的cost由总cost最高的那个branch决定，求用什么方法排列这一列数使生成的树cost最低。

例如，1，2，3，4这四个数

C=21+12=33

solution.prolog

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