프롤로그 - 그 합은 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)). 

하위 시퀀스의 길이에 대한 변수가 있다고 가정 해 보겠습니다. 도메인은 0부터 (빈 서브 시퀀스에 해당)부터 목록의 길이로 이동합니다. 가장 긴 시퀀스를 먼저 얻으려면 가장 높은 값부터 시작하여 값을 시도해야합니다.

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

다음 L는 List의 요소의 인덱스에 대응한다 L 변수 목록을 구축 할 수있다. 이 인덱스는 오름차순이어야하므로 두 개의 연속 인덱스간에 을 사용하여 #</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 우리는 정의 옵션 max/1와 labeling/2를 사용

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.