给定现金金额和货币列表生成零钱

Question

我正在尝试用 Prolog 编写一个程序，它做两件事：

接受两个参数，一个整数和一个整数列表
如果可以从第二个元素的某种组合中对第一个参数进行更改，则满足

我想出了一个解决这个问题的方法，允许更改规则统一到硬币事实，例如：

coin(quarter, 25).
coin(dime,10).
coin(nickel,5).
coin(penny,1).

change(0, []).
change(A, [(C, Num)|L]) :- 
    coin(C, V), 
    A >= V, 
    Num is floor(A / V), 
    B is A mod V, 
    change(B, L).

此外，如果您将诸如 change(27,L) 之类的内容传递给解释器，它会生成可用于找零的 25 美分、10 美分、5 美分和便士的所有可能组合，例如：

?- change(27,L).
L = [(quarter, 1),  (penny, 2)] ;
L = [(dime, 2),  (nickel, 1),  (penny, 2)] ;
L = [(dime, 2),  (penny, 7)] ;
L = [(nickel, 5),  (penny, 2)] ;
L = [(penny, 27)] ;
false.

然而，我遇到了麻烦，如何通过简单地将 [25,10,5,1] 之类的货币列表传递给 change 来解决这个问题，使调用看起来像 change(27, [25 ,10,5,1], L).这可能吗？如果可以，如何实现？

Answer 1

所以你实际上非常接近。这基本上是我留下的评论，扩展。让我们为造币类型添加另一个参数。

change(0, _, []).
change(A, Coinage, [(C, Num)|L]) :- 
    member(C=V, Coinage), 
    A >= V, 
    Num is floor(A / V), 
    B is A mod V, 
    change(B, Coinage, L).

我已将 coin(C, V) 替换为此 member(C=V, Coinage) 术语。 member/2 是使您的 Prolog 程序更具动态性的好方法，因为您实际上可以从列表中生成解决方案，而不是查询事实存储。看看结果：

?- change(27, [quarter=25, dime=10, nickel=5, penny=1], Change).
Change = [(quarter, 1),  (penny, 2)] ;
Change = [(dime, 2),  (nickel, 1),  (penny, 2)] ;
Change = [(dime, 2),  (penny, 7)] ;
Change = [(nickel, 5),  (penny, 2)] ;
Change = [(penny, 27)] ;
false.

让我们看看是否应该添加一个 3 美分的硬币，也许上面有一位最近总统的头像：

?- change(27, [quarter=25, dime=10, nickel=5, thripenny=3, penny=1], Change).
Change = [(quarter, 1),  (penny, 2)] ;
Change = [(dime, 2),  (nickel, 1),  (penny, 2)] ;
Change = [(dime, 2),  (thripenny, 2),  (penny, 1)] ;
Change = [(dime, 2),  (penny, 7)] ;
Change = [(nickel, 5),  (penny, 2)] ;
Change = [(thripenny, 9)] ;
Change = [(penny, 27)] ;

看来这是个好主意！

给定现金金额和货币列表生成零钱

Generating change given a cash amount and a list of currency

prolog

coin-change