如何加快该程序的速度?是硬币持有人计算 [英] How can I speed up this program? It is a coin holder calculation

问题描述

因此，这是一个程序，在其中计算要携带的特定数量的硬币上最少的硬币数量.该程序可以运行，但是速度太慢...当您将值的长度替换为7或更短时，它可以运行...但是，当值等于或大于8时，它确实非常慢.有什么办法可以加快这个程序的速度吗?

So this is a program where it calculates the fewest number of coins to carry with certain values on these coins. The program works, but it's way too slow... When you replace the length of the values 7 or less, it works... But 8 or above, it's really, really slow. Is there any way to speed up this program?

% LIBRARIES NEEDED FOR FUNCTION TO WORK
:- lib(ic).
:- lib(ic_global).
:- lib(branch_and_bound).

questionSix(Values, Coins) :-
    init_vars(Values, Coins),
    coin_cons(Values, Coins, Pockets),
    clever_cons(Values, Coins),
    Min #= sum(Coins),
    minimize((labeling(Values), labeling(Coins), check(Pockets)), Min).

init_vars(Values, Coins) :-
    length(Values, 8),
    occurrences(5, Values, 1),
    Values :: 1..99,
    increasing(Values),
    length(Coins, 8),
    Coins :: 0..99.

increasing(List) :-
    ( fromto(List, [This, Next | Rest], [Next | Rest], [_])
    do
        This #< Next
    ).

clever_cons(Values, Coins) :-
    ( fromto(Values, [V1 | NV], NV, []), 
      fromto(Coins, [N1 | NN], NN, [])
     do
        ( NV = [V2 | _]
            -> N1*V1 #< V2;
            N1*V1 #< 100
        )
    ).

coin_cons(Values, Coins, Pockets) :-
    ( for(Price, 1, 99),
    foreach(CoinsforPrice, Pockets),
    param(Coins, Values)
    do
        price_cons(Price, Coins, Values, CoinsforPrice)
    ).

price_cons(Price, Coins, Values, CoinsforPrice) :-
    ( foreach(V, Values), foreach(C, CoinsforPrice), foreach(Coin, Coins),
    foreach(Prod, ProdList)
    do
        Prod = V*C,
        0 #=< C,
        C #=< Coin
    ),
    Price #= sum(ProdList).

check(Pockets) :-
    ( foreach(CoinsforPrice, Pockets)
    do
        once(labeling(CoinsforPrice))
    ).

感谢您的帮助！谢谢！

推荐答案

首次观察:如果将labeling(Coins)放在labeling(Values)之前，则时间将大大缩短.粗略地说，这是因为在此问题中，硬币的数量比硬币的价值更为重要.

First observation: if you put labeling(Coins) before labeling(Values), the time improves dramatically. Roughly speaking, that's because in this problem number of coins is much more important than values of coins.

第二个观察结果:无论您允许多少个值，您都不能获得少于7个硬币.这是因为如果您使用7个值运行程序，则可以看到在最佳解决方案中每个硬币都被使用了一次.因此，如果您使用的值超过7个，则将仅使用其中的7个，否则硬币的数量将超过7个，并且解决方案不是最佳的.

Second observation: you can't get less than 7 coins no matter how many values you allow. That's because if you run your program with 7 values, you can see that every coin is used once in the optimal solution. So if you have more than 7 values, only 7 of them will be used, or the number of coins will be more than 7 and the solution will be not optimal.

记住这些观察，您就可以更改

With these observations in mind, you can just change

minimize((labeling(Values), labeling(Coins), check(Pockets)), Min).

到

bb_min((labeling(Coins), labeling(Values), check(Pockets)), Min, bb_options{from:7}).

这篇关于如何加快该程序的速度?是硬币持有人计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！