Subset sum Prolog

Question

定義一個謂詞子集（L，Sum，Subl），其中包含一個數列表L，一個數字Sum，並且將SubL與L的子序列合併，使得SubL中的數字總和爲Sum。

例如

?- subsetsum([1,2,5,3,2], 5, SubSet); 

    SubSet = [1,2,2]; 
    SubSet = [2,3]; 
    SubSet = [5]; 
    SubSet = [3,2]; 

No. 

我們

sum([H1 | [H2 | Tail]], S):- 
    sum([[H1+H2]|Tail], S):- 
sum([X], X). 

和

subset([],[]). 
    subset([H1|T1], [H1|T2]) :- // heads are the same 
    subset(T1, T2). 
    subset([_|Rest], X): 
    subset(Rest, X). 

Answer 1

下列條款應該做你需要什麼...

subsetsum(SET, SUM, ANSWER) :- 
    % Find a subset 
    subset(SET, ANSWER), 
    % Check elements of the subset add up to SUM 
    sum(ANSWER, SUM). 

% sum(LIST, SUM) - sums all numbers in the list 
sum([], 0). 
sum([X | T], SUM) :- 
    sum(T, TAILSUM), 
    SUM is TAILSUM + X. 

% subset - finds subsets 
subset([], []). 
subset([E|Tail], [E|NTail]) :- 
    subset(Tail, NTail). 
subset([_|Tail], NTail) :- 
    subset(Tail, NTail). 

Answer 2

With swi-prolog我們可以使用圖書館謂詞sum_list/2以及您已經擁有的subset/2！請注意，我給subset/2更好的擬合名list_subsequence/2：

 
list_subsequence([], []). 
list_subsequence([X|Xs], [X|Ys]) :- 
    list_subsequence(Xs, Ys). 
list_subsequence([_|Xs], Ys) :- 
    list_subsequence(Xs, Ys). 

subsetsum(List, Sum, Sub) :- 
    list_subsequence(List, Sub), 
    sum_list (Sub, Sum). 

這裏是你給的示例查詢：

?- subsetsum([1,2,5,3,2], 5, Xs). 
    Xs = [1,2,2] 
; Xs = [2,3] 
; Xs = [5] 
; Xs = [3,2] 
; false. 

OK！讓我們用整數和浮點數運行另一個查詢......它也能工作嗎？

 
?- subsetsum([1,2.1,5,3,2], 5.1, Xs). 
    Xs = [1,2.1,2] 
; Xs = [2.1,3] 
; false. 

看起來好了給我！

Answer 3

如果所有使用的數字都是整數，並且您的Prolog處理器支持clpfd，請繼續操作！

 
:- use_module (library(clpfd)). 

z_z_product(A,B,AB) :- 
    AB  #= A*B. 

subsetsum_(Zs, Sum, Bs, [Sum|Vs]) :- 
    same_length (Zs, Bs), 
    append (Zs, Bs, Vs), 
    Bs  ins 0..1, 
    maplist (z_z_product, Zs, Bs, Xs), 
    sum (Xs, #=, Sum). 

樣品查詢：

 
?- subsetsum_([1,2,5,3,2], 5, Sel, Vs), labeling ([], Vs). 
    Sel = [0,0,0,1,1], Vs = [5,1,2,5,3,2,0,0,0,1,1] 
; Sel = [0,0,1,0,0], Vs = [5,1,2,5,3,2,0,0,1,0,0] 
; Sel = [0,1,0,1,0], Vs = [5,1,2,5,3,2,0,1,0,1,0] 
; Sel = [1,1,0,0,1], Vs = [5,1,2,5,3,2,1,1,0,0,1] 
; false.