Prolog 将钱分成更小的数额

Question

我有这个谓词 returns 如果 S 等于某个方程 K + 2N + 3L = S 则为真。 我们拥有的钱是 1、5 , K, N, L 分别为 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.

这将 "magically" 变成一个 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.

的选项也可能达到同样的效果

Prolog 将钱分成更小的数额

Prolog Break Money into Smaller Amounts

prolog