序言 - 如何找到最大的一套組件，它們的和等於N

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在任意兩個連續索引之間創建約束。

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

---

由於我不知道這是一門功課與否，我不會在這裏發佈完整的代碼。

Answer 2

在這個答案，我們使用clpfd和一點點lambda：

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

基於meta-predicatemaplist/4和約束(ins)/2和sum/3我們定義：使用labeling/2與選項max/1

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

示例查詢：

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