1

给定一个可能的和数列表，我想确定哪些（如果有的话）可以形成一个给定的总和。例如，使用 [1,2,3,4,5]，我可以将 9 与 [4,5]、[5,3,1] 和 [4,3,2] 相加。我正在使用 GNU Prolog 并且有类似以下的东西不起作用

numbers([1,2,3,4,5]).

all_unique(_, []).
all_unique(L, [V|T]) :-
    fd_exactly(1, L, V),
    all_unique(L, T).

fd_sum([], Sum).
fd_sum([H|T], Sum):-
    S = Sum + H,
    fd_sum(T, S).
    
sum_clp(N, Summands):-
    numbers(Numbers),
    length(Numbers, F),
    between(1, F, X),
    length(S, X),
    fd_domain(S, Numbers),
    fd_domain(Y, [N]),
    all_unique(S, Numbers),
    fd_sum(S, Sum),
    Sum #= Y,
    fd_labeling(S).

我认为主要问题是我没有正确表示对总和的约束？或者也许是别的东西？

4

2 回答 2

2

我认为将代码sublist混入 clp 代码会造成一些混乱。GNU-Prolog有一个sublist/2谓词，你可以使用它。

您似乎正在构建算术表达式，fd_sum但执行不正确。

sum_exp([], 0).
sum_exp([X|Xs], X+Xse) :-
    sum_exp(Xs, Xse).

sum_c(X, N, Xsub) :-
    sublist(Xsub, X),
    sum_exp(Xsub, Xe),
    N #= Xe.

| ?- sum_exp([A, B, C, D], X).

X = A+(B+(C+(D+0)))

yes

| ?- sum_c([1, 2, 3, 4, 5], 9, X).

X = [4,5] ? ;

X = [2,3,4] ? ;

X = [1,3,5] ? ;

(1 ms) no

| ?- length(X, 4), sum_c(X, 4, [A, B]), member(A, [1, 2, 3]).

A = 1
B = 3
X = [_,_,1,3] ? ;

A = 2
B = 2
X = [_,_,2,2] ? ;

A = 3
B = 1
X = [_,_,3,1] ? 

yes
于 2021-10-31T15:47:00.880 回答
2

以防万一您真的对 CLP(FD) 感兴趣，这里是您更正的程序。

numbers([1,2,3,4,5]).

% note: use builtins where available, both for efficiency and correctness
%all_unique(_, []).
%all_unique(L, [V|T]) :-
%    fd_exactly(1, L, V),
%    all_unique(L, T).

fd_sum([], 0). % sum_fd_SO.pl:8: warning: singleton variables [Sum] for fd_sum/2
fd_sum([H|T], Sum):-
    % note: use CLP(FD) operators and the correct operands
    Sum #= S + H,
    fd_sum(T, S).
    
sum_clp(N, S):- % sum_fd_SO.pl:13-23: warning: singleton variables [Summands] for sum_clp/2
    numbers(Numbers),
    length(Numbers, F),
    between(1, F, X),
    length(S, X),
    fd_domain(S, Numbers),
    %fd_domain(Y, [N]),
    %all_unique(S, Numbers),
    fd_all_different(S),
    fd_sum(S, N),
    %Sum #= Y,
    fd_labeling(S).

测试

 ?- sum_clp(3,L).

L = [3] ? ;

L = [1,2] ? ;

L = [2,1] ? ;

no
于 2021-10-31T17:50:39.097 回答