| Stamping Out Stamps |
The mail clerk for Sirius Cybernetics just received a new postal scale which will display the cost (in cents) to send a given parcel. The postal scale is medium duty, and will only handle parcels requiring up to $29.99 in postage. She has requested you to write a program that will convert the postage into the number of stamps needed to cover the required postage such that the cost is minimized.
The mailroom stocks up to ten different types of stamps, and only ten stamps will fit on any given parcel.
Your program would read in a list of stamp values stocked by the mailroom (all separated by single spaces) followed by a sequence of amounts to convert (one amount per line). If it is impossible to reach the given amount exactly, you are to exceed the amount by as little as possible. If there are many sets of stamps that cover the amount for the same cost, you should pick the set with the least number of stamps.
Output should consist of the given stamp values on a single line followed by a blank line, then, for each amount given, the amount that needs to be covered on a single line, followed by the stamps needed for the coverage on the next line, followed by a blank line. (So the last line of stamp values in the output is followed by one blank line.) All numbers are separated by single spaces. If no solution exists, print
NO SOLUTION EXISTS
2 7 14 17 22 63 98 72 86 143 5
STAMP VALUES 2 7 14 17 22 63 98 AMOUNT 72 STAMPS USED 63 7 2 AMOUNT 86 STAMPS USED 63 14 7 2 AMOUNT 143 STAMPS USED 63 63 17 AMOUNT 5 STAMPS USED 2 2 2