Coin-Changing Problems (Dynamic Programming)

% ways/3 finds the number of different ways of giving change for a sum of money
% fewest/3 finds the coins in a solution having the fewest coins

/* ways(Coins, Amount, NumberOfWays) is true if NumberOfWays is the number   */
/*   of ways of making the Amount of money from unlimited quantities of      */
/*   Coins of the given denominations. The Coins must be sorted in           */
/*   ascending order of sequence.                                            */
/* e.g. ways([1,5,10,25,50], 198, X). gives X=2240                           */
ways(Coins, Amount, NumberOfWays):-
  replicate(Amount, 0, FirstRow),
  ways_1(Coins, Amount, FirstRow, LastRow),
  last(LastRow, NumberOfWays).

ways_1([], _, LastRow, LastRow).
ways_1([Coin|Coins], Amount, PreviousRow, LastRow):-
  ways_2(1, Amount, Coin, PreviousRow, [1], NextRow),
  ways_1(Coins, Amount, NextRow, LastRow).

% If I >= Coin then Item = PreviousRow[I] + CurrentRow[I - Coin]
%              else Item = PreviousRow[I]
ways_2(I, Amount, _, _, _, []):-
  I > Amount, !.
ways_2(I, Amount, Coin, PreviousRow, RowSoFar, [Item|NextRow]):-
  % RowSoFar is the reversed list of elements so far in the next
  %   row except that 1 is appended as its first element (at the end)
  nth_member(PreviousRow, I, Item1), !,
  ways_3(I, Coin, RowSoFar, Item1, Item),
  I1 is I + 1,
  ways_2(I1, Amount, Coin, PreviousRow, [Item|RowSoFar], NextRow).
  
ways_3(I, Coin, RowSoFar, Item1, Item):-
  I >= Coin,
  nth_member(RowSoFar, Coin, Item2), !,
  Item is Item1 + Item2.
ways_3(_, _, _, Item, Item).

/* fewest(Coins, Amount, Change) is true if Change is a smallest collection  */
/*   of coins chosen from the denominations in Coins such that the sum of    */
/*   the collection is equal to Amount. The Coins must be sorted in          */
/*   ascending order of sequence.                                            */
/* e.g. fewest([1,5,10,25,50], 198, X). gives X=[1,1,1,10,10,25,50,50,50]    */
fewest(Coins, Amount, Change):-
  replicate(Amount, 32766, FirstRow),
  fewest_1(Coins, Amount, FirstRow, [], [LastRow|Table]),
  reverse(Coins, ReversedSet),
  fewest_4(Amount, ReversedSet, Table, LastRow, ReversedChange),
  reverse(ReversedChange, Change).

fewest_1([], _, LastRow, Table, [LastRow|Table]).
fewest_1([Coin|Coins], Amount, PreviousRow, Table0, Table):-
  fewest_2(1, Amount, Coin, PreviousRow, [0], NextRow),
  fewest_1(Coins, Amount, NextRow, [PreviousRow|Table0], Table).

% If I >= Coin then Item = min(PreviousRow[I], 1 + CurrentRow[I - Coin])
%              else Item = PreviousRow[I]
fewest_2(I, Amount, _, _, _, []):-
  I > Amount, !.
fewest_2(I, Amount, Coin, PreviousRow, RowSoFar, [Item|NextRow]):-
  % RowSoFar is the reversed list of elements so far in the next
  %   row except that 0 is appended as its first element (at the end)
  nth_member(PreviousRow, I, Item1), !,
  fewest_3(I, Coin, RowSoFar, Item1, Item),
  I1 is I + 1,
  fewest_2(I1, Amount, Coin, PreviousRow, [Item|RowSoFar], NextRow).
  
fewest_3(I, Coin, RowSoFar, Item1, Item):-
  I >= Coin,
  nth_member(RowSoFar, Coin, Item2), !,
  Temp is Item2 + 1,
  minimum(Temp, Item1, Item).
fewest_3(_, _, _, Item, Item).

fewest_4(0, _, _, _, []):-!.
fewest_4(I, [_|Coins], [PreviousRow|Table], CurrentRow, Change):-
  nth_member(CurrentRow, I, Item),
  nth_member(PreviousRow, I, Item), !,
  fewest_4(I, Coins, Table, PreviousRow, Change).
fewest_4(I, Coins, Table, CurrentRow, [Coin|Change]):-
  Coins=[Coin|_],
  I1 is I - Coin,
  fewest_4(I1, Coins, Table, CurrentRow, Change).

/* last(Xs, X) is true if X is the last element of the list Xs.              */
last([X], X):-!.
last([_|Xs], X):-last(Xs, X).

/* minimum(X, Y, Z) is true if Z is the minimum of the numbers X and Y.      */
minimum(X, Y, Z):-X =< Y, !, Z=X.
minimum(_, Y, Y).

/* nth_member(+Xs, ?N, ?X) is true if X is the N-th (base 1) element of the  */
/*   list Xs.                                                                */
nth_member(Xs, N, X):-nth_member_1(Xs, X, 1, N).

nth_member_1([X|_], X, I, I).
nth_member_1([_|Xs], X, I0, I):-
  I1 is I0 + 1,
  nth_member_1(Xs, X, I1, I).
  
/* replicate(N, X, Xs) is true if the list Xs contains N occurrences of the  */
/*   item X.                                                                 */
replicate(0, _, []):-!.  
replicate(I, X, [X|Xs]):-
  I > 0,
  I1 is I - 1,
  replicate(I1, X, Xs).

/* reverse(Xs, Ys) is true if Ys is the result of reversing the order of the */
/*   elements in the list Xs.                                                */
%reverse(Xs, Ys):-reverse_1(Xs, [], Ys).

%reverse_1([], As, As).
%reverse_1([X|Xs], As, Ys):-reverse_1(Xs, [X|As], Ys).

LPA Index     Home Page