Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- % The Postage Stamp Problem
- % Running GNU Prolog 1.3.1 on Windows 7
- % Given the maximum number of stamps and a set of stamp denominations
- % This program should print to screen the maximum amount of coverage
- % that the denominations can fill on an envelope
- % so if you have test(1, 5, [1, 4, 12, 21]).
- % 1 is the test case; 5 is the max stamps on the envelope
- % 1, 4, 12, 21 are the stamp denominations
- % That would return 71, as 72 can not be created with a max size of 5
- % allowed stamps on the envelope.
- test(1, 5, [1, 4, 12, 21]). % from in01.txt
- test(2, 10, [1, 7, 16, 31, 88]). % from in01.txt
- test(3, 6, [1, 5, 7, 8]). % from in01.txt
- test(4, 5, [1, 4]). % from in02.txt
- test(5, 6, [1, 2, 3, 7, 11]). % from in03.txt
- test(6, 7, [1, 5, 9]). % from in03.txt
- test(7, 6, [2, 3, 7, 11]). % from in05.txt
- test(8, 7, [5, 9]). % from in05.txt
- test(9, 10, [1]). % from in06.txt
- test(10, 10, [1, 3]). % from in06.txt
- runtest(N, C) :- test(N, Width, Stamps), maxcoverage(C, Width, Stamps).
- maxcoverage(Max, StampsCount, Stamps):-
- maxcoverage(0, StampsCount, Stamps, Max),
- Max > 0.
- maxcoverage(Previous, StampsCount, Stamps, Max):-
- Current is Previous + 1,
- (realize(StampsCount, Stamps, Current) -> % Tries current value.
- maxcoverage(Previous, StampsCount, Stamps, Max) % When succeeds, tries more.
- ;
- Max = Previous % Else returns prvious value as max.
- ).
- realize(StampsCount, Stamps, Value):-
- (Value = 0 ->
- true
- ;
- StampsCount > 0,
- Value > 0,
- member(Stamp, Stamps),
- ValCount is Value - Stamp,
- VValue is Value - 1,
- realize(VValue, Stamps, ValCount)
- ).
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement