Prolog

Question

我的游戏是从给定列表中选择元素的最大集合，它们的总和为 N

示例：L=[1,1,2,2,3,2,4,5,6]、N = 6，子列表等于 [1,1,2,2]

我需要使用约束逻辑编程的提示。

Answer 1

SWI-Prolog 中有一个用于约束逻辑编程的库。它被称为 clpfd。

:-use_module(library(clpfd)).

假设您有一个子序列长度的变量。它的域从零（对应于空子序列）到列表的长度。为了首先获得最长的序列，应该从最高的开始尝试值。

...
    length(List, M),
    L in 0..M,
    labeling([max(L)],[L]),
...

接下来，L 可用于构建 L 变量列表，该列表对应于 List 中的元素索引。由于这些索引必须按升序排列，chain/2 可用于在任意两个连续索引之间创建 #</2 约束。

...
    length(Indices, L),
    Indices ins 1..M,
    chain(Indices, #<),
...

使用这些索引，可以构造一个包含来自 List 的元素的列表。 nth1/3 在这里很有用，但有一个小技巧。

...
nth1a(List, N, E):-
    nth1(N, List, E).
...
    maplist(nth1a(List), Indices, SubSequence),
...

并且该列表的总和必须是 N:

...
    sum(SubSequence, #=, N)
...

由于只需要最长的序列，once/1可以在找到第一个解后停止。

一些示例查询：

?- longest_subsequence([1,1,4,4,6], 9, S).
S = [1, 4, 4].

?- longest_subsequence([1,1,4,4,6], 11, S).
S = [1, 4, 6].

?- longest_subsequence([1,1,4,4,6], 21, S).
false.

因为我不确定这是否是作业，所以我不会post 完整代码在这里。

Answer 2

在这个答案中我们使用 clpfd and a little lambda:

:- use_module([library(clpfd),
               library(lambda)]).

基于meta-predicate maplist/4 and the constraints (ins)/2 and sum/3我们定义：

zs_selection_len_sum(Zs, Bs, L, S) :-
   same_length(Zs, Bs),
   Bs ins 0..1,
   maplist(\Z^B^X^(X #= Z*B), Zs, Bs, Xs),
   sum(Bs, #=, L),
   sum(Xs, #=, S).

使用 labeling/2 和选项 max/1 的示例查询：

?- zs_selection_len_sum([1,1,4,4,6],Bs,L,8), labeling([max(L)],Bs).
  Bs = [1,1,0,0,1], L = 3
; Bs = [0,0,1,1,0], L = 2
; false.

?- zs_selection_len_sum([1,1,3,4,5],Bs,L,7), labeling([max(L)],Bs).
  Bs = [1,1,0,0,1], L = 3 
; Bs = [0,0,1,1,0], L = 2
; false.

?- zs_selection_len_sum([1,1,2,2,3,2,4,5,6],Bs,L,6), labeling([max(L)],Bs).
  Bs = [1,1,0,1,0,1,0,0,0], L = 4
; Bs = [1,1,1,0,0,1,0,0,0], L = 4
; Bs = [1,1,1,1,0,0,0,0,0], L = 4
; Bs = [0,0,1,1,0,1,0,0,0], L = 3
; Bs = [0,1,0,0,1,1,0,0,0], L = 3
; Bs = [0,1,0,1,1,0,0,0,0], L = 3
; Bs = [0,1,1,0,1,0,0,0,0], L = 3
; Bs = [1,0,0,0,1,1,0,0,0], L = 3
; Bs = [1,0,0,1,1,0,0,0,0], L = 3
; Bs = [1,0,1,0,1,0,0,0,0], L = 3
; Bs = [1,1,0,0,0,0,1,0,0], L = 3
; Bs = [0,0,0,0,0,1,1,0,0], L = 2
; Bs = [0,0,0,1,0,0,1,0,0], L = 2
; Bs = [0,0,1,0,0,0,1,0,0], L = 2
; Bs = [0,1,0,0,0,0,0,1,0], L = 2
; Bs = [1,0,0,0,0,0,0,1,0], L = 2
; Bs = [0,0,0,0,0,0,0,0,1], L = 1
; false.

Prolog - 如何找到其总和等于 N 的最大元素集

Prolog - How to find the maximum set of elements that their sum is equal to N

constraint-programming

clpfd