找零钱的方案数以及所需最少张数的钞票的方案

问题描述：

我们知道人民币有1元，2元，5元，10元，20元，50元，100元这几种表示，现在给你一个整数 n  让你找零，求出有多少种方案。

例如  n=4，则方案可为1+1+1+1，2+2,  1+1+2，总共3种。

方案一 ：笨方法

 100a+50b+20c+10d+5e+2f+g=n，a,b,c,d,e,f,g分别为各种面值钞票的张数。通过穷举和限制条件可以求出方案数

方案二：动态规划

 方案一针对的是有限个面值，局限性太大。下面就推出动态规划的方法

我们 规定 f(n,i) 为找零n的所有方案数，其中 i 是找零数组   RMB[]={1,2,5,10,20,50,100} 的最大可找零钱的下标。

举个具体的例子，比如说你有6块钱，那么你最大可找零的钞票是5，那么此时的 i 就是2.

找零的原来很简单，要么包括 最大可找零钞票，要么不包括。

由此可演化出 递归公式   f(  n,  i )= f(n-RMB[i], i)+f(n, i-1);        // 第一项为包括 RMB[i] 的方案数，第二项为不包括的方案数

具体的实现代码：

import java.util.Scanner;

public class zhaolingqian {

	private static int count=0;
	static int RMB[]={1,2,5,10,20,50,100};

	public static void main(String[] args) {
		// TODO Auto-generated method stub
         // 100a+50b+20c+10d+5e+2f+g=n
		Scanner in=new Scanner(System.in);
		while (in.hasNextInt()) {
			int n=in.nextInt();
			if (n==0) {
				break;
			}
			
			//  笨方法。
			/*count=0;
			for (int a = 0; a <=n/100; a++) {
				for (int b = 0; b <=n/50; b++) {
					for (int c = 0; c <=n/20; c++) {
						for (int d = 0; d <=n/10; d++) {
							for (int e = 0; e <=n/5; e++) {
								for (int f = 0; f <=n/2; f++) {
									for (int g = 0; g <=n; g++) {
										if(100*a+50*b+20*c+10*d+5*e+2*f+g==n) {
											count++;
											continue;
										}
											
											
									}
								}
							}
						}
					}
				}
			}
			System.out.println(count);*/
			
			
			
			
			
			//  动态规划方法
			int i=0;
			for ( i = 6; i >=0&&RMB[i]>n; i--) ;  // 找到最大的可找零钱的下标
			System.out.println(find(n,2));
			
			
		}
		
		
		
		
	}
	
	// 找到可找零钱的方案数
	private static int find(int n, int i) {
		// TODO Auto-generated method stub
		if (n<0) {
			return 0;
		}
		if (n<=1||RMB[i]==1) {
			return 1;
		}
		
		
		return find(n-RMB[i], i)+find(n, i-1);        // 第一项为包括 RMB[i] 的方案数，第二项为不包括的方案数
	}

}

进阶： 怎么找到 最少张数的钞票的方案 ？

我们采用自下而上的动态规划方法

import java.util.Scanner;

public class dtghZhaoLing {
	static int RMB[]={1,2,5,10,20,50,100};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		
		  Scanner in=new Scanner(System.in);
		  while (in.hasNext()) {
			  int n=in.nextInt();
	          int res[][]=f (n);
	          while(n>0){
	        	  System.out.println(res[1][n]);
	        	  n=n-res[1][n];
	          }
		}
		 
          
	}
	private static int[][] f(int n) {
		// TODO Auto-generated method stub
		int s[][]=new int[2][n+1];
		s[0][0]=0;
		
		for (int i = 1; i <=n; i++) {
			int q=n;
			int k=0;
			for ( k = 6; k >=0&&RMB[k]>n; k--) ;   // 找到最大的可找零钱的下标
			for (int j = 0; j <=k; j++) {
				if (i>=RMB[j]&&q>=1+s[0][i-RMB[j]]) {
					q=1+s[0][i-RMB[j]];
					s[1][i]=RMB[j];
				}
			}
			
			s[0][i]=q;
		}
		return s;
	}

}