试用 Prolog 语言解算法题

现有一列随机的正整数,算他有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.

% 计算节点Cost = 左子树数字和 * 右子树数字和
element_cost(List, Cost) :-
  bisect(List, Left, Right),
  sum_list(Left, LeftSum),
  sum_list(Right, RightSum),
  Cost is (LeftSum * RightSum).

% 计算整树Cost = 节点Cost + Max(左子树Cost, 右子树Cost)
% (叶子节点的整树Cost = 0)
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).

% 所有可能的树和树Cost
all_cost(List, TargetList, Cost) :-
  permutation(List, TargetList),
  tree_cost(TargetList, Cost).

% 获得最小的树Cost
min_cost(List, Cost) :-
  findall(TargetCost, all_cost(List, _, TargetCost), CostList),
  min_list(CostList, Cost).

% 获得最小的树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).