时间戳

首页 > 解决方案 > 如何找到长度不大于列表长度三分之一且元素总和最大的列表的子列表

prolog - 如何找到长度不大于列表长度三分之一且元素总和最大的列表的子列表

问题描述

如何找到长度不大于列表长度三分之一的列表的子列表，并且在 Prolog 中其元素的总和最大？

标签： prolog

解决方案

由于这里没有足够的问题可以回答，这里有一些解决此类 Prolog 问题的一般建议。

您可以使用未绑定的列表参数创建指定长度length/2的列表，例如：

?- length(X, 3).
X = [_3192, _3198, _3204].

这在尝试回答涉及列表的问题时通常很有用。您可以获取列表的长度，然后length/2再次使用来构造结果列表。

select/3也是回答这类问题的有用谓词，因为它可用于从列表中挑选项目。例如，如果我想从列表中选择两个项目，我可以这样做：

picktwo(L, [X,Y]) :- select(X, L, L0), select(Y, L0, _).

在这里，我将返回这两个项目，忽略列表的其余部分，这些列表将在我_现在的位置上可用。

?- picktwo([7,18,3,4,19], X).
X = [7, 18] ;
X = [7, 3] ;
X = [7, 4] ;
X = [7, 19] ;
X = [18, 7] ;
X = [18, 3] ;
X = [18, 4] ;
X = [18, 19] ;
X = [3, 7] ;
X = [3, 18] ;
X = [3, 4] ;
X = [3, 19] ;
X = [4, 7] ;
X = [4, 18] .

（像我这样的 DCG 粉丝可能会对这种替代实现感到好笑phrase((select(X), select(Y)), [7,18,3,4,19], _).：）

有一个用于汇总列表的内置程序，称为sumlist/2.

最大化问题通常可以通过要求 Prolog 找到比所有其他解决方案更大的解决方案来以一种漂亮但效率极低的方式解决。此类代码通常如下所示：

solve(Solution) :- 
   find_solution(Solution), 
   \+ (find_solution(Solution2), Solution2 > Solution1).

在这里，您声明式地表示解决方案是最好的，因为没有其他更好的解决方案。Prolog 当然必须做组合的事情来找到最好的解决方案，所以这肯定会将可能是 O(N log N) 的搜索变成 O(N^2) 的搜索，但是对于小数据来说它可以正常工作套。这是查找最大值对的示例：

sumpairs(List, X, Y, Sum) :- 
    select(X, List, L0), select(Y, L0, _), Sum is X + Y.

largest(List, X, Y) :- 
    sumpairs(List, X, Y, Sum), 
    \+ (sumpairs(List, _, _, ABSum), ABSum > Sum).

这会产生：

?- largest([7,18,3,4,19], X, Y).
X = 18,
Y = 19 ;
X = 19,
Y = 18 ;
false.

所以你可以看到它是如此的低效，它实际上通过排列两次找到了相同的答案，但如果你关心的话，你可能会想一些方法来防止这种情况发生。

这盒零件可能足以让您自己找到问题的答案，祝您好运！

推荐阅读