Подмножество sum Пролог

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

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