【蓝桥杯-筑基篇】贪心

野性酷女 2024-04-20 07:50 81阅读 0赞

> ?系列专栏:[蓝桥杯][Link 1]
> 
> ?个人主页:[个人主页][Link 2]

**目录**

1.找零问题

①暴力枚举

②贪心

2.人性总是贪婪的

3.堆果子

4.图书推荐

--------------------

### 1.找零问题 ###

有币种**1**、**2**、**4**、**5**、**10**若干张，找零`n`元，输出找零方案。

#### ①暴力枚举 ####

这是一个找零问题，我们需要找到一种方案，使得用给定的硬币找零时，所需的硬币数量最少。

在这个代码中，我们使用了暴力枚举的思路，即枚举每种硬币的数量，然后判断是否能够凑出目标金额。如果能够凑出目标金额，则输出方案。

这种方法的时间复杂度为 O(n^5)，因为我们需要枚举每种硬币的数量，而硬币的种类有 5 种，所以总共需要枚举 5 层循环。

这种方法的优点是代码简单易懂，容易实现。缺点是时间复杂度较高，不适用于大规模数据的处理。

public class A {
        public static void main(String[] args) {
            int[] coins = {1, 2, 4, 5, 10};
            int target = 18;
            int count = 0;
            for (int i = 0; i <= target / coins[0]; i++) {
                for (int j = 0; j <= target / coins[1]; j++) {
                    for (int k = 0; k <= target / coins[2]; k++) {
                        for (int l = 0; l <= target / coins[3]; l++) {
                            for (int m = 0; m <= target / coins[4]; m++) {
                                if (i * coins[0] + j * coins[1] + k * coins[2] + l * coins[3] + m * coins[4] == target) {
                                    count++;
                                    System.out.println("方案" + count + ": " + i + "个1元+" + j + "个2元+" + k + "个4元+" + l + "个5元+" + m + "个10元");
                                }
                            }
                        }
                    }
                }
            }
        }
    }

方案1: 0个1元+0个2元+2个4元+0个5元+1个10元
    方案2: 0个1元+0个2元+2个4元+2个5元+0个10元
    方案3: 0个1元+1个2元+4个4元+0个5元+0个10元
    方案4: 0个1元+2个2元+1个4元+0个5元+1个10元
    方案5: 0个1元+2个2元+1个4元+2个5元+0个10元
    方案6: 0个1元+3个2元+3个4元+0个5元+0个10元
    方案7: 0个1元+4个2元+0个4元+0个5元+1个10元
    方案8: 0个1元+4个2元+0个4元+2个5元+0个10元
    方案9: 0个1元+5个2元+2个4元+0个5元+0个10元
    方案10: 0个1元+7个2元+1个4元+0个5元+0个10元
    方案11: 0个1元+9个2元+0个4元+0个5元+0个10元
    方案12: 1个1元+0个2元+3个4元+1个5元+0个10元
    方案13: 1个1元+1个2元+0个4元+1个5元+1个10元
    方案14: 1个1元+1个2元+0个4元+3个5元+0个10元
    方案15: 1个1元+2个2元+2个4元+1个5元+0个10元
    方案16: 1个1元+4个2元+1个4元+1个5元+0个10元
    方案17: 1个1元+6个2元+0个4元+1个5元+0个10元
    方案18: 2个1元+0个2元+4个4元+0个5元+0个10元
    方案19: 2个1元+1个2元+1个4元+0个5元+1个10元
    方案20: 2个1元+1个2元+1个4元+2个5元+0个10元
    方案21: 2个1元+2个2元+3个4元+0个5元+0个10元
    方案22: 2个1元+3个2元+0个4元+0个5元+1个10元
    方案23: 2个1元+3个2元+0个4元+2个5元+0个10元
    方案24: 2个1元+4个2元+2个4元+0个5元+0个10元
    方案25: 2个1元+6个2元+1个4元+0个5元+0个10元
    方案26: 2个1元+8个2元+0个4元+0个5元+0个10元
    方案27: 3个1元+0个2元+0个4元+1个5元+1个10元
    方案28: 3个1元+0个2元+0个4元+3个5元+0个10元
    方案29: 3个1元+1个2元+2个4元+1个5元+0个10元
    方案30: 3个1元+3个2元+1个4元+1个5元+0个10元
    方案31: 3个1元+5个2元+0个4元+1个5元+0个10元
    方案32: 4个1元+0个2元+1个4元+0个5元+1个10元
    方案33: 4个1元+0个2元+1个4元+2个5元+0个10元
    方案34: 4个1元+1个2元+3个4元+0个5元+0个10元
    方案35: 4个1元+2个2元+0个4元+0个5元+1个10元
    方案36: 4个1元+2个2元+0个4元+2个5元+0个10元
    方案37: 4个1元+3个2元+2个4元+0个5元+0个10元
    方案38: 4个1元+5个2元+1个4元+0个5元+0个10元
    方案39: 4个1元+7个2元+0个4元+0个5元+0个10元
    方案40: 5个1元+0个2元+2个4元+1个5元+0个10元
    方案41: 5个1元+2个2元+1个4元+1个5元+0个10元
    方案42: 5个1元+4个2元+0个4元+1个5元+0个10元
    方案43: 6个1元+0个2元+3个4元+0个5元+0个10元
    方案44: 6个1元+1个2元+0个4元+0个5元+1个10元
    方案45: 6个1元+1个2元+0个4元+2个5元+0个10元
    方案46: 6个1元+2个2元+2个4元+0个5元+0个10元
    方案47: 6个1元+4个2元+1个4元+0个5元+0个10元
    方案48: 6个1元+6个2元+0个4元+0个5元+0个10元
    方案49: 7个1元+1个2元+1个4元+1个5元+0个10元
    方案50: 7个1元+3个2元+0个4元+1个5元+0个10元
    方案51: 8个1元+0个2元+0个4元+0个5元+1个10元
    方案52: 8个1元+0个2元+0个4元+2个5元+0个10元
    方案53: 8个1元+1个2元+2个4元+0个5元+0个10元
    方案54: 8个1元+3个2元+1个4元+0个5元+0个10元
    方案55: 8个1元+5个2元+0个4元+0个5元+0个10元
    方案56: 9个1元+0个2元+1个4元+1个5元+0个10元
    方案57: 9个1元+2个2元+0个4元+1个5元+0个10元
    方案58: 10个1元+0个2元+2个4元+0个5元+0个10元
    方案59: 10个1元+2个2元+1个4元+0个5元+0个10元
    方案60: 10个1元+4个2元+0个4元+0个5元+0个10元
    方案61: 11个1元+1个2元+0个4元+1个5元+0个10元
    方案62: 12个1元+1个2元+1个4元+0个5元+0个10元
    方案63: 12个1元+3个2元+0个4元+0个5元+0个10元
    方案64: 13个1元+0个2元+0个4元+1个5元+0个10元
    方案65: 14个1元+0个2元+1个4元+0个5元+0个10元
    方案66: 14个1元+2个2元+0个4元+0个5元+0个10元
    方案67: 16个1元+1个2元+0个4元+0个5元+0个10元
    方案68: 18个1元+0个2元+0个4元+0个5元+0个10元

#### ②贪心 ####

给定一个需要找零的金额money和一些硬币的面值，计算出最少需要使用多少个硬币才能找零。具体实现是，从大到小遍历硬币面值，每次尽可能使用面值大的硬币，直到找零金额为0为止。在遍历过程中，记录使用的硬币数量和面值，并输出。最后输出使用的硬币数量。

public static void main(String[] args) {
        int[] coins = {10, 5, 4, 2, 1};
        int money = 18;
        // 输出需要找零的金额
        System.out.println("需要找零" + money + "元");
    
        int count = 0;
        for (int i = 0; i < coins.length; i++) {
            while (money >= coins[i]) {
                money -= coins[i];
                count++;
                // 输出使用的硬币面值
                System.out.println("使用了面值为" + coins[i] + "的硬币");
            }
        }
        // 输出使用的硬币数量
        System.out.println("一共使用了" + count + "个硬币");
    }

需要找零18元
    使用了面值为10的硬币
    使用了面值为5的硬币
    使用了面值为2的硬币
    使用了面值为1的硬币
    一共使用了4个硬币

### 2.人性总是贪婪的 ###

假如整数n表示当前奖池中已经有的钱的总数，给你一个一夜暴富的机会：请你从n中删除m个数字，余下的数值对应的金额就是你能够拿走的钱，我们知道人性都是贪婪的，那么请编程帮小明使得余下的数字按原次序组成的新数最大，比如当n=92081346718538. m=10时，则新的最大数是9888

**样例输入**

92081346718538 10
    1008908 5

**样例输出**

9888
    98

主要思路是：从左到右遍历字符串，每次选出当前可选范围内最大的数字，直到选出n-m个数字为止。

以`n=92081346718538`. `m=10`为例 :

例如要保留4位数。

第一位数 ，从下标0到下标10取， 要余3位【下标：11，12，13】

第二位数，要余2位【下标：12，13】

第三位数，要余1位【下标：13】

如下图：

![1bb9298006c84edeb46b63842c06426b.png][]

具体实现上，程序使用了一个char数组来存储输入的字符串，使用了一个last\_select\_pos变量来记录上一次选出的数字的位置，以避免重复选取。在每次选取数字时，程序从last\_select\_pos+1的位置开始遍历，直到可选范围内的最后一个数字，选出其中最大的数字，并更新last\_select\_pos的值。最后将选出的数字串输出即可。

import java.util.Scanner;
    
    public class selectMoney {
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		while (sc.hasNext()) {
    			String n = sc.next();// 用字符串的形式读入进来
    			int m = sc.nextInt();// 要删除的个数
    			int save = n.length() - m;// 保留的个数，删除问题转换成保留的问题
    			String max = "";// 存放最后我们选择要保留的字符
    			char[] a = n.toCharArray();// n变成字符数组
    			int last_select_pos = -1;// 开始的时候一个都没有被选中+1刚好对应0的位置
    			for (int i = 1; i <= save; i++) {// 分save次去选择每次可选的最大字符
    				char big = '0';// 假定本轮要选的字符是无穷小
    				for (int j = last_select_pos+1; j < a.length - (save - i); j++) {
    					if (a[j] > big) {
    						big = a[j];
    						last_select_pos = j;// 记录当前找到的最大的位置
    					}
    				}
    				max = max + big;// 每一次都把找到的可选的最大的字符串追加到尾部
    			}
    			System.out.println(max);
    		}
    	}
    }

###  ###

### 3.堆果子 ###

**题目描述：**

在一个果园里，多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并,多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。 多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。

假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有3种果子，数目依次为1, 2, 9。可以先将1、2堆合并,新堆数目为3,耗费体力为3。  
接着，将新堆与原先的第三堆合并，又得到新的堆,数目为12,耗费体力为12。  
所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

**输入:**

![01aaaa39b9c449a6bbfa6a2bc57066bf.png][]

**样例输入**

5
    1 2 3 4 5

**样例输出**

**思路：将数据存入数组内**

**对数组进行排序，然后将最小的2个值相加【重复此步骤】**

5
    1 2 3 4 5
    ------------------------------
    [1, 2, 3, 4, 5]
    arr[i]:1
    arr[i+1]:2
    [0, 3, 3, 4, 5]
    arr[i]:3
    arr[i+1]:3
    [0, 0, 4, 5, 6]
    arr[i]:4
    arr[i+1]:5
    [0, 0, 0, 6, 9]
    arr[i]:6
    arr[i+1]:9
    [0, 0, 0, 0, 15]
    ------------------------------
    33

//导入Scanner和Arrays类
    import java.util.Scanner;
    import java.util.Arrays;
    
    public class A {
    	public static void main(String[] args) {
    		//创建Scanner对象
    		Scanner sc = new Scanner(System.in);
    		//读取输入的整数n
    		int n=sc.nextInt();
    		//创建长度为n的整型数组arr
    		int arr[]=new int[n];
    		//定义变量number并初始化为0
    		int number=0;
    		//循环读取n个整数并存入数组arr中
    		for (int j = 0; j < arr.length; j++) {
    			arr[j]=sc.nextInt();
    		}
    		//对数组arr进行排序
    		Arrays.sort(arr);
    		//循环处理数组arr
    		for (int i = 0; i < arr.length-1; i++) {
    			//将arr[i]和arr[i+1]相加并存入arr[i+1]中
    			arr[i+1]=arr[i]+arr[i+1];
    			//将arr[i+1]累加到number中
    			number+=arr[i+1];
    			//将arr[i]赋值为0
    			arr[i]=0;
    			//对数组arr进行排序
    			Arrays.sort(arr);
    		}
    		//输出number
    		System.out.println(number);
    	
    	}
    }

### 4.图书推荐 ###

> 本书以“零基础”为起点，系统地介绍了uni-app的跨平台开发与应用。全书内容分为3篇，共12章，具体安排如下。
> 
> 第一篇：基础篇，包括第1~4章，主要介绍了uni-app的特点和优势、环境搭建、HBuilderX开发工具的安装和使用，以及uni-app的一些基础知识。第二篇：进阶篇，包括第5~9章，主要介绍了uni-app的基础配置、相关组件、导航栏、高效开发技巧，以及uniCloud云开发平台。第三篇：实战篇，包括第10~12章，通过第一个实战，介绍了如何使用uni-app开发小程序；通过第二个实战，介绍了如何使用uni-app进行跨平台开发；通过第三个实战，介绍了如何使用uniCloud云开发。
> 
> 京东自营购买链接：[《uni-app跨平台开发与应用从入门到实践 DCloud/uni-app官方认证教材》][uni-app_ DCloud_uni-app]

![d56acc62db144497b9a67d753ed0c9dc.jpeg][]

[Link 1]: https://blog.csdn.net/javascript_tsj/category_12167433.html
[Link 2]: https://blog.csdn.net/Javascript_tsj?type=blog
[1bb9298006c84edeb46b63842c06426b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/bae9f113e84442f184d1c3730f8ef7d0.png
[01aaaa39b9c449a6bbfa6a2bc57066bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/3a4f3b41a99a42d2b68987f71aa53af8.png
[uni-app_ DCloud_uni-app]: https://item.jd.com/13389767.html
[d56acc62db144497b9a67d753ed0c9dc.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/52b782cba3c6489b91220ec07e0d50c7.jpeg