一道算法题：在超市用现金结账时，有以下几种纸币，arr[] =[100,50,20,5,1]

，现在求我如何付钱以及收银员如何找钱，才能使付给收银员张数和收银员找回的张数加起来最少？比如我结账需付19，我可以付20，然后收银员找1，这样只需要2张钱，数量最少。

参加某线下笔试，有这么一道选做题。。。。。。。。

思路：

假设理应当付A块，现在实际付了B块，则要解决两个问题：表达B块最少多少张钱？表达B-A块最少多少张钱？枚举下B，取两个最小值的和的最小值即可。B取[A,100+A)肯定对。

表达n块最少需要多少张钱这就成了一个经典的完全背包问题。参见背包九讲的完全背包一节。当然value不是最大化而是最小化。

作者：Tim Shen

下面是自己的实现

import java.util.Arrays;import java.util.Scanner;/* * 在超市用现金结账时，有以下几种纸币，arr[] =[100,50,20,10,5,1],现在求我如何付钱以及收银员如何找钱，才能使付给收银员张数和收银员找回的张数加起来最少？比如我结账需付19，我可以付20，然后收银员找1，这样只需要2张钱，数量最少。 */public class coinChange {	public static void main(String[] args) {		Scanner in = new Scanner(System.in);		int[] coins = {1,5,10,20,50,100};		int target = in.nextInt();		int ret = Integer.MAX_VALUE;		int bb = 0;		for(int B=target;B
     
       (t1+t2)){				ret = t1 + t2;				bb = B;			}			//ret = Math.min(ret, t1+t2);		}		//System.out.println(bb);		System.out.println(ret);	}	 public static int coinChange(int[] coins, int amount) {	        if(amount==0)return 0;	    int[] min=new int [amount+1];	    Arrays.fill(min,amount+1);	    min[0]=0;	    for(int i=1;i<=amount;i++){	    for(int j=0;j