Stampcalculator - Given a set of stamps, what combinations are there to reach a certain amount?

Background

My mother has a hobby of buying and reselling books via online trading sites. After a price is agreed on, the books have to be put into an envelope for mailing. On this envelope, stamps have to be applied to pay for postage (mailing fee). My mother buys stamps in bulk at various prices, varying from 75 to 90% of face value. As the postage prices change every year, new stamp combinations have to be calculated that will satisfy the postage fee with a minimum amount of hassle.

My mother is not all that good with calculations. And having to manually recalculate what stamp combinations are best to get to the postage required for a 250 - 500 gram package takes a lot of time. Therefore, she calculates a few options via trial and error - sometimes overshooting the postage amount by a few cents - and just uses those.

Some stamps are preferred to be used, whereas others aren't, due to the cost not always being the face value of a stamp. Asking my mother about the stamp prices individually would have taken too much time, so I just made a program that generates a list of options. It requires recompilation when you need to add different stamps or want to get to a different limit, but that's okay. The whole point of this was to not spend too much time on it (the goal is to save time!) - which is why I wrote it in the total time of 1 hour (from idea to solution).

Problem description

Given a target amount, a set of stamp denominations, and a maximum amount of usable stamps, print a list of stamp combinations that will get to the target amount.

Programmed in 1 hour. I have placed everything in one file to ensure that it can run in Ideone, so that she could theoretically make the changes herself, if needed.

How it works

Using a list of stamps, make partial combinations that are at or below the target amount. For each combination, make a new combinations via duplicating the current combination and adding a stamp with a value equal to or below the last added stamp. C

if (collection.getSum() == GOAL) {
                    solutions.add(collection);
                    continue;
                }

and

if (newOne.getSum() == GOAL) {
                        solutions.add(newOne);
                    } else {

are redundant. The only time that the first one triggers is if you can meet the solution with a single stamp. So you could do without the second one and just always add to inProgress, or you can move the first one.

for (int i = 0; i < stamps.length; i++) {
            inProgress.add(new StampCollection(stamps[i]));
        }

could be

for (int stamp: stamps) {
            StampCollection collection = new StampCollection(stamp);
            if (stamp == GOAL) {
                solutions.add(collection);
            } else if (stamp < GOAL) {
                inProgress.add(collection);
            }
        }

Then you don't have to check for that on each iteration of the other loop.

I would prefer this form of for loop, since you only use i as an array index.

But you don't actually need to do that. Instead, you could replace that section with

inProgress.add(new StampCollection());

and change getLastStampValue to

public int getLastStampValue() {
            return stamps.isEmpty() ? Integer.MAX_VALUE : stamps.peekLast();
        }

So that it doesn't try to compare a null.

private static List solutions;

    private static List inProgress;

These don't need to be class fields. They could just be local variables.

System.out.println("Found " + solutions.size() + " solutions");

        for (StampCollection solution : solutions) {
            if (solution.getSum() == GOAL) {
                System.out.println(solution);
            } else {
                System.out.println("WTF: " + solution);
            }
        }

could be

List solutions = calculateSolutions(stamps, 292);

        System.out.println("Found " + solutions.size() + " solutions");
        for (StampCollection solution : solutions) {
            System.out.println(solution);
        }

This would move most of the logic out of main, and it reduces the code, as the else never happens.

public static List calculateSolutions(int[] stamps, int goal) {
        List solutions = new ArrayList<>();
        List inProgress = new ArrayList<>();

        inProgress.add(new StampCollection());

        while (!inProgress.isEmpty()) {
            List nextWave = new ArrayList<>();
            for (StampCollection collection : inProgress) {
                if (collection.getStamps().size() >= STAMP_LIMIT) {
                    continue;
                }

                for (int stamp : stamps) {
                    if (stamp > collection.getLastStampValue() || (collection.getSum() + stamp) > goal) {
                        continue;
                    }

                    StampCollection newOne = new StampCollection(collection, stamp);
                    if (newOne.getSum() == goal) {
                        solutions.add(newOne);
                    } else {
                        nextWave.add(newOne);
                    }
                }
            }

            inProgress = nextWave;
        }

        return solutions;
    }

Now if you want, you could call this method from another class in the same package. And you could call the method multiple times with different goals.

StackExchange Code Review Q#135652, answer score: 3