Created
July 20, 2023 07:50
-
-
Save jvlmdr/c7c6702240ef7d0986e9a3dd919428c5 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
:- table fewest_coins/3. | |
fewest_coins(_, 0, []). | |
fewest_coins(Coins, Target, Change) :- | |
Target > 0, | |
convlist(solve_subproblem(Coins, Target), Coins, Solutions), | |
min_member(length_leq, Change, Solutions). | |
length_leq(A, B) :- length(A, LenA), length(B, LenB), LenA =< LenB. | |
solve_subproblem(Coins, Target, Coin, Change) :- | |
plus(SubTarget, Coin, Target), | |
fewest_coins(Coins, SubTarget, SubChange), | |
Change = [Coin | SubChange]. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
fewest_coins([1, 5, 10, 25], 1, Change). | |
fewest_coins([1, 5, 10, 25, 100], 25, Change). | |
fewest_coins([1, 5, 10, 25, 100], 15, Change). | |
fewest_coins([1, 4, 15, 20, 50], 23, Change). | |
fewest_coins([1, 5, 10, 21, 25], 63, Change). | |
fewest_coins([1, 2, 5, 10, 20, 50, 100], 999, Change). | |
fewest_coins([2, 5, 10, 20, 50], 21, Change). | |
fewest_coins([4, 5], 27, Change). | |
fewest_coins([1, 5, 10, 21, 25], 0, Change). | |
fewest_coins([5, 10], 3, Change). | |
fewest_coins([5, 10], 94, Change). | |
fewest_coins([1, 2, 5], -5, Change). |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Change = [1]. | |
Change = [25]. | |
Change = [5, 10]. | |
Change = [4, 4, 15]. | |
Change = [21, 21, 21]. | |
Change = [2, 2, 5, 20, 20, 50, 100, 100, 100|...]. | |
Change = [2, 2, 2, 5, 10]. | |
Change = [4, 4, 4, 5, 5, 5]. | |
Change = []. | |
false. | |
false. | |
false. | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
swipl -f change.pl <in.txt >out.txt |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment