Stamps

This is a explanation of this problem from USACO's training website. I have converted it to markdown. Please do not just copy code; you will not learn anything; at least type it out and understand so you can do it yourself in the future!

Given a set of N stamp values (e.g., {1 cent, 3 cents}) and an upper limit K to the number of stamps that can fit on an envelope, calculate the largest unbroken list of postages from 1 cent to M cents that can be created.

For example, consider stamps whose values are limited to 1 cent and 3 cents; you can use at most 5 stamps. It’s easy to see how to assemble postage of 1 through 5 cents (just use that many 1 cent stamps), and successive values aren’t much harder:

6 = 3 + 3
7 = 3 + 3 + 1
8 = 3 + 3 + 1 + 1
9 = 3 + 3 + 3
10 = 3 + 3 + 3 + 1
11 = 3 + 3 + 3 + 1 + 1
12 = 3 + 3 + 3 + 3
13 = 3 + 3 + 3 + 3 + 1.

However, there is no way to make 14 cents of postage with 5 or fewer stamps of value 1 and 3 cents. Thus, for this set of two stamp values and a limit of K=5, the answer is M=13.

The most difficult test case for this problem has a time limit of 3 seconds.

PROGRAM NAME: stamps

INPUT FORMAT

Line 1:	Two integers K and N. K (1 <= K <= 200) is the total number of stamps that can be used. N (1 <= N <= 50) is the number of stamp values.
Line 2..end:	N integers, 15 per line, listing all of the N stamp values, each of which will be at most 10000.

SAMPLE INPUT (file stamps.in)

5 2
1 3

OUTPUT FORMAT

Line 1:

One integer, the number of contiguous postage values starting at 1 cent that can be formed using no more than K stamps from the set.

SAMPLE OUTPUT (file stamps.out)

CODE

Java

C++

Pascal

ANALYSIS

Alex Schwendner

This problem is simply begging for a DP solution. We keep an array “minstamps” such that minstamps[i] is the minimum number of stamps needed to make i cents. For each stamp type, we try adding one stamp of that type to each number of cents that we have already made. After we have found the minimum number of stamps needed to make any given number of cents, we find the smallest number of cents that we cannot make with the given number of stamps, and then we output one less then that.

#include <fstream.h>

const int BIG = 10000;

short   minstamps[10000 * (200 + 3) + 3];
int     stamps;
int     value[200];
int     number;


int 
main ()
{

    ifstream filein ("stamps.in");
    filein >> number >> stamps;
    int     biggest = -1;
    for (int i = 0; i < stamps; ++i) {
	filein >> value[i];
	if (biggest < value[i]) {
	    biggest = value[i];
	}
    }
    filein.close ();

    for (int i = 0; i <= biggest * number + 3; ++i) {
	minstamps[i] = BIG;
    }

    minstamps[0] = 0;
    for (int i = 0; i < stamps; ++i) {
	for (int j = 0; j <= biggest * number; ++j) {
	    if (minstamps[j] < number) {
		if (minstamps[j + value[i]] > 1 + minstamps[j]) {
		    minstamps[j + value[i]] = 1 + minstamps[j];
		}
	    }
	}
    }


    int     string = 0;
    while (minstamps[string + 1] <= number) {
	++string;
    }

    ofstream fileout ("stamps.out");
    fileout << string << endl;
    fileout.close ();

    return (0);
}