蓝桥杯全排列扩展（找零钱问题-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);//如果凑不到就直接Noifa(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也清零，等下一次的maxmax = 0;//找到i的值，如果i都遍历了，说明都能找钱，后续就是输出YESnas = i;}if(nas==ui-1) {System.out.println("YES");}}