Prolog将资金分成更小的金额

Question

我有这个谓词,如果S等于某个等式,即K + 2N + 3L = S,则返回true .对于K,N,L,我们分别为1,5和10.

我不想使用:- use_module(library(clpfd)),我想在没有它的情况下解决这个问题.

我的直觉是将其分解为像写函数一样的子问题breakMoney1(S,K) :- K is S.并且添加了一个参数创建了更多帮助器,但是当我比较时,我正在努力解决获取未实例化变量的问题.

 breakMoney(S,K,N,L) :- 

Answer 1

这可能比你想象的要容易.@Will Ness建议之后的一个非常天真的解决方案是:

break(Sum, K, N, L) :- integer(Sum), Sum >= 0,

    % upper bounds for K, N, and L
    K_Max is Sum div 1,
    N_Max is Sum div 5,
    L_Max is Sum div 10,

    % enumerate possible values for K, N, and L
    between(0, L_Max, L),
    between(0, N_Max, N),
    between(0, K_Max, K),

    Sum =:= K + 5*N + 10*L.

这将"神奇地"变成CLP(FD)解决方案,用很少的努力:比如,更换between用X in 0..Max和=:=用#=.虽然,仅仅说出X #>= 0每个面额就足够了.看看你可以删除多少限制并仍然得到答案是一个很好的练习:

break(Sum, K, N, L) :-
    K #>= 0, N #>= 0, L #>= 0,
    Sum #= K + 5*N + 10*L.

根据您实例化参数的方式,您可能会立即获得唯一的答案,或者您可能需要使用label/1:

?- break(100, P, 8, 5).
P = 10.

?- break(10, K, N, L).
K in 0..10,
-1*K+ -5*N+ -10*L#= -10,
N in 0..2,
L in 0..1.

?- break(10, K, N, L), label([K, N, L]).
K = N, N = 0,
L = 1 ;
K = L, L = 0,
N = 2 ;
K = 5,
N = 1,
L = 0 ;
K = 10,
N = L, L = 0.

但正如@lurker所指出的那样,没有理由不对这个问题使用约束编程.当然,除非您有一个非常聪明的算法来解决这个特定的问题,并且您知道它将超越通用的clp(fd)解决方案.即使这样,也可以通过使用选项来实现相同的效果labelling/2.