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).

Sale!