YoungProgrammer

Problem 8: Given a set of integers( 1000,500,100,50,20,10,5,4,1). Write a program which will take a number as input ( let N) and outputs the least integers(let n1, n2...) from the set so that n1 + n2 + ... = N
Example: for input 25, output will be:
20 5
( 2 integers only)
but will not be 10 10 5 or 5 5 5 5 5 etc.

Solution: We will try to use height numbers first, then the lower one. For an example, N = 750
we can not use 1000, so take the next one, 500. Our remaining amount is 750-500 = 250. We can not use 500 any more, move to the next one, 100. We can use it 2 times. The remaining amount is 50. Next we can use 50 one time. Our final result is: 500 100 100 50

Source Code:

#include<stdio.h>

int main() {
	int SET[] = {1000,500,100,50,20,5,4,1};
	int N, i;
	scanf("%d",&N);
	for(i = 0; i<8; i++) {
		while(SET[i] <= N) {
			printf("%d ",SET[i]);
			N -= SET[i];
		}
	}
	printf("\n");
	return 0;
} 

Note: This approach will not work for every case. Try 8, you will able to find the reason.