Prolog 将资金分成较小的金额 [英] Prolog Break Money into Smaller Amounts
问题描述
我有这个谓词,如果 S 等于某个等式,则返回 true,例如 K + 2N + 3L = S. 对于 K、N,我们拥有的钱分别为 1、5 和 10,L.
I have this predicate which returns true if S is equal to some equation say K + 2N + 3L = S. The money we have are 1, 5, and 10 respectively for K, N, L.
我不想使用:- use_module(library(clpfd))
,我想在没有它的情况下解决这个问题.
I don't want to use :- use_module(library(clpfd))
, I want to solve this without it.
我的直觉是把它分解成子问题,比如写一个函数 breakMoney1(S,K) :- K is S
.并创建更多的助手,添加一个更多的参数,但是当我比较时,我正在努力解决获取未实例化变量的问题.
My intuition was to break this into subproblems like write a function breakMoney1(S,K) :- K is S
. and create more helpers with one more parameter added however I am struggling with the problem of getting uninstantiated variables, when I compare.
breakMoney(S,K,N,L) :-
推荐答案
这可能比您想象的要容易.按照@Will Ness 的建议,一个非常幼稚的解决方案是:
This is easier than you think, probably. A very naive solution following @Will Ness' suggestion would be:
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
就足够了.这是一个很好的练习,看看您可以删除多少约束并仍然得到答案:
This will "magically" turn into a clp(fd) solution with very little effort: for example, replace between
with X in 0..Max
, and the =:=
with #=
. Although, it should be enough to simply say that X #>= 0
for each of the denominations. It is a good exercise to see how much of the constraints you can remove and still get an answer:
break(Sum, K, N, L) :-
K #>= 0, N #>= 0, L #>= 0,
Sum #= K + 5*N + 10*L.
根据您如何实例化参数,您可能会立即得到唯一的答案,或者您可能需要使用 label/1
:
Depending on how you instantiate the arguments, you might immediately get a unique answer, or you might need to use 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
的选项来达到相同的效果.
But as @lurker has pointed out, there is very little reason not to use constraint programming for this problem. Unless, of course, you have a very clever algorithm for solving this particular problem and you know for a fact that it will outsmart the generic clp(fd) solution. Even then, it might be possible to achieve the same effect by using the options to labelling/2
.
这篇关于Prolog 将资金分成较小的金额的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!