Machine Problem 4 Choosing Postage Stamps

ECE220: Computer Systems & Programming 
Machine Problem 4 
Choosing Postage Stamps
Your task this week is to solve an optimization problem and to print the solution. The problem involves
selecting the correct combination of “postage stamps” to affix to a package in order to exceed a required
amount. Specifically, given a required postage cost and four different stamp values, you must write a
C function that selects the best number of each type of stamp. “Best” is defined as a combination of stamps
with total value of at least the postage cost, but otherwise minimal. If ties in total value are possible with
different combinations of stamps, your function must select a combination with the smallest number of
stamps. If ties are still possible, your function must select the combination with the largest number of
stamps with the highest value (then maximize the number of stamps with second-highest value, and so
forth). Abstractly, the problem can be viewed as an algorithmic problem, an optimization problem, and in
some cases as a number theory problem. But don’t spend too much time worrying about the math: the
objective for this week is for you to gain some experience with control structures in C, particularly with
loops and conditional statements.
Background
Finding the right combination of stamps is an optimization problem. But why is this problem challenging?
In practice, it’s usually not. Before electronic commerce, merchants solved this problem thousands of times
a day in their heads. To make the problem easier, monetary systems (both coins and bills) use specific
combinations of values, always including the basic unit of currency. Similarly, selecting postage stamps
has also been fairly straightforward, although the reasons for the simplicity are not as good, at least in the
U.S., where postage costs are always multiples of the current large stamp value, and the post office issued
numerous small stamps for those with outdated “large” stamps when prices rose.
Let’s start with some simple examples, using stamp values typical of monetary systems, such as 10, 5, 2,
and 1. With these values, the problem can be solved using a greedy approach, in which we start with the
biggest value and work down towards the smallest, choosing the number of stamps of each type. For a cost
of 79, for example, we first observe that we can use 7 stamps of value 10, leaving 9 (=79 – 10×7) more to
cover. Moving to the stamp of value 5, we decide to use 1, leaving 4 more to cover. Adding 2 stamps of
value 2 then brings our total to 79, and we are done, having used 0 stamps of value 1. Using a correct
version of our program, we would type the command on the left and see the answer as shown on the right:
./stamps 79 10 5 2 1 prints 7 1 2 0 -> 79 (and a newline).
Greedy algorithms are easy to write and often produce reasonable results, but they don’t always solve the
problem precisely. Imagine that our stamp values are now 50, 25, 10, 1, and that we want to produce the
value 30. Following a greedy approach, we select 0 stamps of value 50, 1 stamp of value 25, 0 stamps of
value 10, and 5 stamps of value 1, for a total of 6 stamps. If we instead use 3 stamps of value 10, however,
we cover the cost of 30 using only 3 stamps! A correct version of our program, of course, must produce
the correct answer:
./stamps 30 50 25 10 1 prints 0 0 3 0 -> 30 (and a newline).
Similar problems arise when the smallest stamp value is larger than 1. Consider the stamp values 50, 25,
10, and 3. What if the amount needed is 17? A greedy approach gives 1 stamp of value 10 and 3 stamps
of value 3, totaling 19. In fact, obtaining a value of 17 is not possible with these stamp values, but neither
is 19 the best choice: by using 6 stamps of value 3, we reduce the total cost to 18, even though we end up
using more stamps. And, again, a correct program must find this answer:
./stamps 17 50 25 10 3 prints 0 0 0 6 -> 18
 (exact match not possible) (+newline)
Note the extra line of text, which is printed by the code given to you based on the return value from your
function.
Ties in both cost and number of stamps may seem impossible at first, but they are actually fairly easy to
find. Consider, for example, a value of 5 with stamp values 4, 3, 2, and 1. With a correct program, we
observe:
./stamps 5 4 3 2 1 prints 1 0 0 1 -> 5 (and a newline).
For some combinations of stamp values, we can solve the problem using modular arithmetic, making it
more of a number theory problem. For example, consider stamp values 30, 15, 10, and 6. If we choose A,
B, C, and D of each, respectively, we obtain total value V = 30A + 15B + 10C + 6D. If V is the desired
value, we must have (V = B) mod 2, (V = C) mod 3, and (V = D) mod 5. And then A must be maximized
by converting multiples of the smaller stamps into those with value 30. For example, if we want a total of
995, we have A = 32, B = 1, C = 2, and D = 0.
Sometimes problems that are easy to solve in practice are tricky to solve in general.
The Task
You must write the C function specified by the following:
int32_t print_stamps (int32_t amount, int32_t s1, int32_t s2,
 int32_t s3, int32_t s4);
The first parameter passed to print_stamps is the amount of postage needed, which will always be
positive. The other four parameters are the stamp values in decreasing order. All stamp values are positive,
and are strictly decreasing (no two values will be the same).
Your C function must determine the combination of stamps that
 has total value no less than the required amount,
 but otherwise has minimum total value.
If multiple combinations exist with the minimum total value, your function must choose the combination
that uses the minimum total number of stamps. If ties in both value and number are possible, your function
must choose the combination with the largest number of the most valuable stamp (s1). If ties are still
possible, maximize the number of the second most valuable stamp (s2), and so forth.
For the chosen combination, your function must print the four numbers of stamps chosen in decimal,
separated by spaces, followed by “ -> “ (four characters, including a leading and trailing space), the total
value of the chosen combination in decimal, and a newline (“\n”). Printing should be easy with printf,
but your format must match ours exactly to receive credit.
Finally, your function must return 1 if the value of the chosen combination matches the required amount
exactly, or 0 otherwise.
The “(exact match not possible)” line is not printed by your function, but rather by the code
provided to you based on the return value from your function. Do not print that line in your code!
The intent of this assignment is not for you to invent clever algorithmic approaches. Simply use loops
(iterations) to consider every reasonable combination of stamps, and use conditional statements to identify
the best choice. If you design your loops in the right way, your code will break some ties naturally, and
your conditionals will be simpler. If you design your loops more simply, your conditionals must check all
of the tie-breaking conditions. Either approach is acceptable: again, we just want you to learn how to write
loops and conditionals and to use variables to solve a problem. Computers are fast, so making them do a
little more work to save humans some thinking time is usually the right answer.
Pieces
Your program will consist of a total of three files:
mp4.h This header file provides function declarations and a brief description of the
function that you must write for this assignment.
mp4.c The main source file for your code (you must write it yourself). Include the
mp4.h header file and be sure that your function matches the one in the header.
A second file is also provided to you:
main.c A source file that interprets commands and calls your function.
You need not read this file, although you are welcome to do so.
We have also provided you with a correct version of the executable, called gold. You can use this program
to generate additional test cases as well as exact output against which to compare your own program.
Specifics
You should read the description of the function in the header file before you begin coding.
 Your code must be written in C and must be submitted as a file named mp4.c. in the mp/mp4
subdirectory of your repository. We will NOT grade any other files. Changes made to any other
files WILL BE IGNORED during grading. If your code does not work properly without such
changes, you are likely to receive 0 credit.
 You must implement the print_stamps function correctly.
o You may assume that the required amount is positive.
o You may assume that all stamp values are positive.
o You may assume that stamp values are unique (not equal) and given in decreasing order:
s1 > s2 > s3 > s4 > 0.
 Your routine’s return values and outputs must be correct.
 Your code must be well-commented. Follow the commenting style of the code examples provided
in class and in the textbook.
Compiling and Executing Your Program
Once you have created the mp4.c file and written the print_row function, you can compile your code by
typing:
gcc -g -Wall main.c mp4.c -o stamps
The “-g” argument tells the compiler to include debugging information so that you can use gdb to find
your bugs (you will have some).
The “-Wall” argument tells the compiler to give you warning messages for any code that it thinks likely
to be a bug. Track down and fix all such issues, as they are usually bugs. Also note that if your code
generates any warnings, you will lose points.
The “-o stamps” argument tells the compiler to name the resulting program “stamps”. If compilation
succeeds, you can then execute the program as specified in the examples given earlier in this document.
The stamps program takes five command line arguments:
./stamps <amount> <s1> <s2> <s3> <s4>
The first argument is the amount of postage needed, and the other four arguments are the region sizes. If
the arguments given are not valid (according to the assumptions given in the “Specifics” section), the code
in main.c responds without calling your function.
Grading Rubric
We put a fair amount of emphasis on style and clarity in this class, as reflected in the rubric below.
Functionality (70%)
 5% - Function returns 1 when amount can be covered exactly, and 0 when it cannot.
 10% - Output matches specified output exactly.
 20% - Function chooses correct combination when no ties in value are possible.
 20% - Function chooses correct combination when no ties in both value and number of coins are
possible.
 15% - Function always chooses correct combination.
Style (15%)
 15% - Loops consider only reasonable combinations of stamps (note, for example, that you need at
most ⌈𝐚𝐦𝐨𝐮𝐧𝐭 / 𝐬𝟏⌉ of the first stamp, where the brackets indicate rounding up to the next integer).
Comments, Clarity, and Write-up (15%)
 5% - introductory paragraph explaining what you did (even if it’s just the required work)
 10% - code is clear and well-commented, and compilation generates no warnings (note: any
warning generated during compilation means 0 points here)
Note that some categories in the rubric may depend on other categories and/or criteria. For example, if you
code does not compile, you will receive no functionality points. Your function must be able to be called
many times and produce the correct results, so we suggest that you avoid using any static storage (or you
may lose most/all of your functionality points).