2818.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2818  User Id:fzk 
Memory:44K  Time:0MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>

int v[] = { 25, 10, 5, 1 };
int total[4][101];
int used[4][100];
int main( ) {
	int amount[4], i, j, sum;
	int a[4];
	while( 1 ) {
		for( i=0; i<4; i++ )
			scanf( "%d", &amount[i] );
		
		scanf( "%d", &sum );
		
		if( amount[0] == 0 &&
			amount[1] == 0 &&
			amount[2] == 0 &&
			amount[3] == 0 &&
			sum == 0 )
			break;
			
		memset( total, -1, sizeof total );
		memset( used, 0, sizeof used ); 
		total[0][0] = 0;
		
		for( i=0; i<4; i++ )
		for( j=0; j<=sum; j++ ){
			if( total[i][j] >= 0  ) {
				if( i<3 && ( total[i+1][j] < 0 || total[i+1][j] > total[i][j] ) ) {
					total[i+1][j] = total[i][j];
					used[i+1][j] = 0;
				}
				if( j+v[i]<=sum && used[i][j] < amount[i] &&
					( total[i][j+v[i]] < 0 || total[i][j]+1 < total[i][j+v[i]] ) ) {
					total[i][j+v[i]] = total[i][j]+1;
					used[i][j+v[i]] = used[i][j]+1;
				}
			}
		}
		if( total[3][sum] < 0 )
			printf( "Cannot dispense the desired amount.\n" );
		else {
			for( i=3; i>=0; i-- ) {
				a[i] = used[i][sum];
				sum -= v[i]*used[i][sum];
			}
			printf( "Dispense %d quarters, %d dimes, %d nickels, and %d pennies.\n",
				a[0], a[1], a[2], a[3] );
		}
		
	}
	return 0;
}