子集和 Prolog

Question

定义一个谓词 subsetsum(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 we can use the library predicate <a href="http://www.swi-prolog.org/pldoc/doc_for?object=sum_list/2" rel="nofollow">sum_list/2</a>连同那个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.

好的！ 让我们运行另一个同时使用整数和浮点数的查询...这也有效吗？

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

子集和 Prolog

Subset sum Prolog

sum

list

prolog

subset

subset-sum