CMSI 186 - Problem Set #2

CMSI 186 - Problem Set #2 Changemaker Redux Due Tuesday, February 17

Overview

For this assignment you will develop a Java program that solves the general problem of making change.

The General Problem of Making Change

Make a program that inputs a set of coins' denominations (positive integers), plus an amount of money (a non-negative integer, expressed in cents), and that outputs the optimal way of making that amount, if possible, or a message indicating that it cannot be done, otherwise.

The set of denominations is not required to include a one-cent coin; consequently, it might not be possible to make the specified amount.

Per our discussion in class, your program will have to make use of special objects called tuples, for which you must make a class. Here's the summary for class Tuple.

You must construct unit tests for class Tuple before you code the methods themselves. Here's some help with the unit tests which also introduces Java's assert statement (comments at the top of the program explain how to compile and run it).

Your program will be invoked like this:
```
    java Changemaker amt c1 ... ck
```
where amt is the amount to be made, and c1, ... , ck, are the coins' denominations.
Your program must reject bad data such as missing arguments, malformed arguments, denominations that aren't positive, duplicated denominations, and negative amounts.

Examples

java Changemaker -4 3 12

should output

improper amount: -4

java Changemaker 63 0 12 3

should output

improper denomination: 0

java Changemaker 63 10 12 3 12

should output

duplicated denomination: 12

java Changemaker 14 8 13 4 9

should output

it is impossible to make 14 cents with coins denominated 8, 13, 4, 9

java Changemaker 14 3 1 9 8

should output

you can make 14 cents with just 3 coin(s) like this:

    2 3-cent coins

    0 1-cent coins

    0 9-cent coins

    1 8-cent coins

Return to: CMSI 186 home page

Revised: February 16, 2009