Introduction

The objective of this assignment is to learn how to use variables, operators, expressions, and console input/output. You will write a program using C++ that determines the number of stamps of various denominations () to be used for a particular postage () in a mail.

Suppose a country issues stamps of six different denominations$1,$2,$3,$4,$5,$6(in decreasing order). Given a particular postage, a strategy to determine the combination of various stamps to be used is as follows. First, use the maximum number of the highest denomination ($1). Then, from the remaining postage, use the maximum number of the second highest denomination ($2). The process continues for the remaining denominations $3, $4, $5, $6. Table 1 and Table 2 show two examples of such stamp amount calculation.

Postage: $127 Stamp Denomination $50 $37 $23 $17 $5 $1 Amount 201004

Table 1: Postage $127 with denominations $50, $37, $23, $17, $5 and $1

Postage: $65 Stamp Denomination $48 $22 $12 $6 $2 $1 Amount 101021

Table 2: Postage $65 with denominations $48, $22, $12, $6, $2, and $1

Note that this strategy does not guarantee the fewest number of stamps used. E.g., a postage of $54 with the denominations in Table 1 can be formed by one $37 stamp and one $17 stamp, but this strategy would give one $50 stamp and four $1 stamps. Besides, it even does not guarantee to find a combination of stamps. E.g., a postage of $8 with denominations $7, $6, $5, $4, $3, $2 can be formed by one $6 stamp and one $2 stamp, but this strategy cannot find a combination after using one $7 stamp.

Program Specification

The program first obtains the six stamp denominations from the user. If the six denominations are not in strict decreasing order, a message Not in decreasing order! would be printed and the program quits. Otherwise, the program further obtains a postage as user input. You can assume all user inputs will always be positive integers. Use the strategy described above to determine the number of stamps of each denomination to be used and print out the result. However, if no stamp combinations can be found, print out a message Cannot find combination!