时间戳

首页 > 解决方案 > 如何使用 fd 求解器确定列表中的哪些元素可以求和为给定数字？

prolog - 如何使用 fd 求解器确定列表中的哪些元素可以求和为给定数字？

问题描述

给定一个可能的和数列表，我想确定哪些（如果有的话）可以形成一个给定的总和。例如，使用 [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).

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

标签： prologclpfdgnu-prolog

解决方案

我认为将代码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

推荐阅读