% 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.
% Finds max value in sequence 1,...,n per problem instance.
% Fails if no such number exists.

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(StampsCount, Stamps, Max):-
    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)
    ).