1

所以这是一个程序，它计算在这些硬币上带有特定值的最少硬币数量。该程序可以工作，但是太慢了...当您将值的长度替换为 7 或以下时，它可以工作...但是 8 或以上，它真的非常慢。有什么办法可以加快这个程序？

% 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))
    ).

任何帮助表示赞赏！谢谢！

4

1 回答 1

1

第一个观察：如果你放labeling(Coins)之前labeling(Values)，时间会显着提高。粗略地说，这是因为在这个问题中，硬币的数量比硬币的价值重要得多。

第二个观察：无论你允许多少个值，你都不能得到少于 7 个硬币。那是因为如果你用 7 个值运行你的程序，你可以看到每个硬币在最优解中被使用一次。因此，如果您的值超过 7 个，则只会使用其中的 7 个，或者硬币的数量将超过 7 个，并且解决方案将不是最优的。

考虑到这些观察结果，您可以更改

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

至

bb_min((labeling(Coins), labeling(Values), check(Pockets)), Min, bb_options{from:7}).
于 2014-05-22T20:42:31.210 回答