思路也是看网上的，不过这种方法很不错。
#include <stdio.h>
#include <memory.h>
#include <limits.h>
#define max(x,y)  ((x)>=(y))?(x):(y)
int dp[10001];
int path[5][10001];
int main()
{	int P,c1,c2,c3,c4;
	int i,j,k;
	int v[5]={0,1,5,10,25},num[5];
	while(~scanf("%d %d %d %d %d",&P,&num[1],&num[2],&num[3],&num[4]))
	{	if(!P&&!num[1]&&!num[2]&&!num[3]&&!num[4])	break;
		memset(dp,-1,sizeof(dp)),dp[0]=0;
		memset(path,0,sizeof(path));
		for(i=1;i<=4;++i)
		{	for(j=v[i];j<=P;++j)
			{	if(dp[j-v[i]]!=-1&&dp[j]<dp[j-v[i]]+1&&path[i][j-v[i]]+1<=num[i])
				{	dp[j]=dp[j-v[i]]+1;
					path[i][j]=path[i][j-v[i]]+1;
					for(k=0;k<i;++k)
						path[k][j]=path[k][j-v[i]];
				}	
			}
		}
		if(dp[P]==-1)	puts("Charlie cannot buy coffee.");
		else
			printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",
				path[1][P],path[2][P],path[3][P],path[4][P]);
	}
	return 0;
}