蓝桥杯全排列扩展（找零钱问题-java详解）

题目：

有n个人正在饭堂排队买海北鸡饭。每份海北鸡饭要25元。奇怪的是，每个人手里只有一张钞票（每张钞票的面值为25、50、100元），而且饭堂阿姨一开始没有任何零钱。请问饭堂阿姨能否给所有人找零（假设饭堂阿姨足够聪明）输入格式第一行一个整数n，表示排队的人数。

接下来n个整数a[1],a[2],…,a[n]。a[i]表示第i位学生手里钞票的价值（i越小，在队伍里越靠前） 　　输出格式： 　　输出YES或者NO 　　样例输入 　　4 　　25 25 50 　　样例输出： 　　YES

整体思路

很显然，这道题是想用回溯的方式来求，如何把客人的钱取出来再找回去，事情先不用这么复杂，我们就先考虑，如果给一串数字，能不能取出其中的数字的和来等于要找的零钱，比如说25，25，50这一串数字，要找50块钱，其中满足条件的有{25，25}，{50}如果能找出这两串数字，那么我们基本上就已经完成这道题目了。 　步骤一： 　和之前的全排列一样，我们先有一个排列组合的意识，之前全排列只是要求把所有的数字举出来，那么我们只需要在他们全排列运算的途中加一下，并且返回出口不再是选择数字的长度等于待排列的数字，而是满足取出数字的和等于、大于、小于目标数的情况，如果等于，那么就选好这串数字，然后返回，如果大于，那么就移除最后一个数字再返回，如果小于就继续把数字加进去 　代码如下：

public class money { //建立一个存储放满足条件的数字的容器 static ArrayList<String> store = new ArrayList(); //定义一个最大值，如果最大值是符合条件的 那必然符合 static int max = 0； List<Integer> w = Arrays.asList(25, 25, 50);//暂时有一个测试串 /*selected：暂时存储容器 choose：待选择容器 to:排序重复的筛选 flag:目标数字*/ public static void run(List<Integer> choose, ArrayList<Integer> selected, ArrayList<Integer> to, int flag) { int count = selected.stream().mapToInt(Integer::intValue).sum();//Integer容器的求和方式 if (count == flag) { max = Math.max(max, count);//如果相等，max就是我们要的，并且我们希望把不重复的selected里面的内容先存起来 if(store.contains((Arrays.toString(selected.toArray())))==false) { store.add(Arrays.toString(selected.toArray())); } return; } /*如果是大于的话，我们就删掉最后一个，当没加入最后那个数字*/ else if (count > flag) { selected.remove(selected.size() - 1); count = selected.stream().mapToInt(Integer::intValue).sum(); max = Math.max(max, count); return; } /*其余情况我们就继续递归*/ else { max = Math.max(max, count); } } }

步骤二： 接下来就和全排列几乎一样，遍历待排列的数字，然后进行回溯 代码补充：

public class money { static ArrayList<String> store = new ArrayList(); static int max = 0; List<Integer> w = Arrays.asList(25, 25, 50); public static void run(List<Integer> choose, ArrayList<Integer> selected, ArrayList<Integer> to, int flag) { int count = selected.stream().mapToInt(Integer::intValue).sum(); if (count == flag) { if(store.contains((Arrays.toString(selected.toArray())))==false) { store.add(Arrays.toString(selected.toArray())); } max = Math.max(max, count); return; } else if (count > flag) { selected.remove(selected.size() - 1); count = selected.stream().mapToInt(Integer::intValue).sum(); max = Math.max(max, count); return; } else { max = Math.max(max, count); } //回溯代码几乎和全排列一模一样 for(int i=0;i<choose.size();i++) { Integer num = choose.get(i); Integer a = i; if(to.contains(a)) { continue; } to.add(a); selected.add(num); run(choose,selected,to,flag); to.remove(a); selected.remove(num); } } }

步骤三： 在步骤三之前，我们先测试一下代码是否可以把满足条件的selected都存入到store容器当中，也就是50能有那些组合

public static void main(String[] args) { ArrayList<Integer> selected = new ArrayList(); ArrayList<Integer> to = new ArrayList(); run(w,selected,to,50); System.out.println(store); }

测试还算是比较ok的，接下来就是处理字符串的问题，现在假设我们能够拿到{25，25}{50}的话，然后我们要找钱，肯定希望把50的先找出去，所以我们需要先拿到一串数字由大到小排列 然后拿到最后一串数字，必然是整钱更多，把这些钱找出去就行了 现在我们的目标就是转化store的字符串，并且拿到最后一个字符串，转为数字

//存储最后那一串转化成int类型的容器 static ArrayList <Integer> last = new ArrayList(); public static void trans(ArrayList <String> goal) { //如果goal里面是空，说明没有数字满足找钱，直接返回，找钱失败 if(goal.size()==0) { return; } //因为前面要把[]去掉，会出现空格，现在把空格也去掉 String fah = goal.get(goal.size()-1).replaceAll(" ",""); String a []; a = fah.split(",");//以“,”为分割符 分割数字 //把数字存入到之前我们准备好的容器当中即可 for(int i=0;i<a.length;i++) { int das = Integer.parseInt(a[i]); last.add(das); } return ; }

测试之后可以发现，我们可以提取出存取进去的最后一串字符的数字，接下来我们就是写主函数，那我们就是循环人数，然后一个一个人的钱试，全部能找完，就YES，中途有人找不了就NO。 主函数：

public static void main(String[] args) throws IOException{ //我用的是Sacnner和io流两种方式来读取键盘内容 BufferedReader iln = new BufferedReader(new InputStreamReader(System.in)); //建立两个容器之前已经说过了 ArrayList <Integer> selected = new ArrayList(); ArrayList <Integer> to = new ArrayList(); //w容器是拿来存储待排列数字的，一个一个遍历 List <Integer> w = new ArrayList();; /*有问题就一步一步测试，看起来会更清楚*/ // run(w,selected,to,flag); // System.out.println(max); // System.out.println(store); // trans(store); // System.out.println(last); Scanner in = new Scanner(System.in); //读取要几个人买 int ui = in.nextInt(); //存储i的值，方便后面好判断是否遍历完了所有的人 int nas = 0; //读取每一个人的钱 String h = iln.readLine(); String [] da = new String [ui]; da = h.split(" "); //开始遍历每一个人手里的钱 for(int i=0;i<ui;i++) { int pi = Integer.parseInt(da[i]); w.add(pi);//不管怎样先把钱放在手里 //如果是25块钱就直接收入囊中，直接跳过找钱 if(pi==25) { continue; } //其他情况就先找到给我的钱-25，看看我剩下的钱有没有可以凑到的 run(w,selected,to,pi-25); trans(store); //如果凑不到就直接No ifa(max!=pi-25) { System.out.println("NO"); break; } //如果能找开，就把我们之前trans出来的数字，把w里面有的删掉，说明这个钱找出去了 for(int k=0;k<last.size();k++) { w.remove(last.get(k)); } //last容器全清空，为下一次找钱做准备 for(int k=0;k<last.size();k++) { last.remove(last.get(k)); } //max也清零，等下一次的max max = 0; //找到i的值，如果i都遍历了，说明都能找钱，后续就是输出YES nas = i; } if(nas==ui-1) { System.out.println("YES"); } }

总结：

整道题目就完成了，总体思路还是比较容易想，回溯思路就可以完成找钱的步骤，难度还算比较大吧！

PS：因为没有测试器测试，我觉得肯定有些逻辑小错误，有什么问题可以及时评论，谢谢喔！