深圳幻海软件技术有限公司 欢迎您!

【蓝桥杯-筑基篇】贪心

2023-04-13

🍓系列专栏:蓝桥杯🍉个人主页:个人主页目录1.找零问题①暴力枚举②贪心2.人性总是贪婪的3.堆果子4.图书推荐1.找零问题有币种1、2、4、5、10若干张,找零n元,输出找零方案。①暴力枚举这是一个找零问题,我们需要找到一种方案,使得用给定的硬币找零时,所需的硬币数量最少。在这个代码中,我们使用

🍓系列专栏:蓝桥杯

🍉个人主页:个人主页

目录

1.找零问题

①暴力枚举

②贪心

2.人性总是贪婪的

3.堆果子

4.图书推荐


1.找零问题

有币种124510若干张,找零n元,输出找零方案。

①暴力枚举

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

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

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

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

  1. public class A {
  2. public static void main(String[] args) {
  3. int[] coins = {1, 2, 4, 5, 10};
  4. int target = 18;
  5. int count = 0;
  6. for (int i = 0; i <= target / coins[0]; i++) {
  7. for (int j = 0; j <= target / coins[1]; j++) {
  8. for (int k = 0; k <= target / coins[2]; k++) {
  9. for (int l = 0; l <= target / coins[3]; l++) {
  10. for (int m = 0; m <= target / coins[4]; m++) {
  11. if (i * coins[0] + j * coins[1] + k * coins[2] + l * coins[3] + m * coins[4] == target) {
  12. count++;
  13. System.out.println("方案" + count + ": " + i + "个1元+" + j + "个2元+" + k + "个4元+" + l + "个5元+" + m + "个10元");
  14. }
  15. }
  16. }
  17. }
  18. }
  19. }
  20. }
  21. }
  1. 方案1: 01元+02元+24元+05元+110
  2. 方案2: 01元+02元+24元+25元+010
  3. 方案3: 01元+12元+44元+05元+010
  4. 方案4: 01元+22元+14元+05元+110
  5. 方案5: 01元+22元+14元+25元+010
  6. 方案6: 01元+32元+34元+05元+010
  7. 方案7: 01元+42元+04元+05元+110
  8. 方案8: 01元+42元+04元+25元+010
  9. 方案9: 01元+52元+24元+05元+010
  10. 方案10: 01元+72元+14元+05元+010
  11. 方案11: 01元+92元+04元+05元+010
  12. 方案12: 11元+02元+34元+15元+010
  13. 方案13: 11元+12元+04元+15元+110
  14. 方案14: 11元+12元+04元+35元+010
  15. 方案15: 11元+22元+24元+15元+010
  16. 方案16: 11元+42元+14元+15元+010
  17. 方案17: 11元+62元+04元+15元+010
  18. 方案18: 21元+02元+44元+05元+010
  19. 方案19: 21元+12元+14元+05元+110
  20. 方案20: 21元+12元+14元+25元+010
  21. 方案21: 21元+22元+34元+05元+010
  22. 方案22: 21元+32元+04元+05元+110
  23. 方案23: 21元+32元+04元+25元+010
  24. 方案24: 21元+42元+24元+05元+010
  25. 方案25: 21元+62元+14元+05元+010
  26. 方案26: 21元+82元+04元+05元+010
  27. 方案27: 31元+02元+04元+15元+110
  28. 方案28: 31元+02元+04元+35元+010
  29. 方案29: 31元+12元+24元+15元+010
  30. 方案30: 31元+32元+14元+15元+010
  31. 方案31: 31元+52元+04元+15元+010
  32. 方案32: 41元+02元+14元+05元+110
  33. 方案33: 41元+02元+14元+25元+010
  34. 方案34: 41元+12元+34元+05元+010
  35. 方案35: 41元+22元+04元+05元+110
  36. 方案36: 41元+22元+04元+25元+010
  37. 方案37: 41元+32元+24元+05元+010
  38. 方案38: 41元+52元+14元+05元+010
  39. 方案39: 41元+72元+04元+05元+010
  40. 方案40: 51元+02元+24元+15元+010
  41. 方案41: 51元+22元+14元+15元+010
  42. 方案42: 51元+42元+04元+15元+010
  43. 方案43: 61元+02元+34元+05元+010
  44. 方案44: 61元+12元+04元+05元+110
  45. 方案45: 61元+12元+04元+25元+010
  46. 方案46: 61元+22元+24元+05元+010
  47. 方案47: 61元+42元+14元+05元+010
  48. 方案48: 61元+62元+04元+05元+010
  49. 方案49: 71元+12元+14元+15元+010
  50. 方案50: 71元+32元+04元+15元+010
  51. 方案51: 81元+02元+04元+05元+110
  52. 方案52: 81元+02元+04元+25元+010
  53. 方案53: 81元+12元+24元+05元+010
  54. 方案54: 81元+32元+14元+05元+010
  55. 方案55: 81元+52元+04元+05元+010
  56. 方案56: 91元+02元+14元+15元+010
  57. 方案57: 91元+22元+04元+15元+010
  58. 方案58: 101元+02元+24元+05元+010
  59. 方案59: 101元+22元+14元+05元+010
  60. 方案60: 101元+42元+04元+05元+010
  61. 方案61: 111元+12元+04元+15元+010
  62. 方案62: 121元+12元+14元+05元+010
  63. 方案63: 121元+32元+04元+05元+010
  64. 方案64: 131元+02元+04元+15元+010
  65. 方案65: 141元+02元+14元+05元+010
  66. 方案66: 141元+22元+04元+05元+010
  67. 方案67: 161元+12元+04元+05元+010
  68. 方案68: 181元+02元+04元+05元+010

②贪心

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

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

2.人性总是贪婪的

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


样例输入

  1. 92081346718538 10
  2. 1008908 5

样例输出

  1. 9888
  2. 98

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

n=92081346718538m=10为例 :

例如要保留4位数。

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

第二位数,要余2位【下标:12,13】

第三位数,要余1位【下标:13】

如下图:

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

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

3.堆果子

题目描述:

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

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

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

输入:

 样例输入

  1. 5
  2. 1 2 3 4 5

样例输出

33

思路:将数据存入数组内

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

  1. 5
  2. 1 2 3 4 5
  3. ------------------------------
  4. [1, 2, 3, 4, 5]
  5. arr[i]:1
  6. arr[i+1]:2
  7. [0, 3, 3, 4, 5]
  8. arr[i]:3
  9. arr[i+1]:3
  10. [0, 0, 4, 5, 6]
  11. arr[i]:4
  12. arr[i+1]:5
  13. [0, 0, 0, 6, 9]
  14. arr[i]:6
  15. arr[i+1]:9
  16. [0, 0, 0, 0, 15]
  17. ------------------------------
  18. 33
  1. //导入Scanner和Arrays类
  2. import java.util.Scanner;
  3. import java.util.Arrays;
  4. public class A {
  5. public static void main(String[] args) {
  6. //创建Scanner对象
  7. Scanner sc = new Scanner(System.in);
  8. //读取输入的整数n
  9. int n=sc.nextInt();
  10. //创建长度为n的整型数组arr
  11. int arr[]=new int[n];
  12. //定义变量number并初始化为0
  13. int number=0;
  14. //循环读取n个整数并存入数组arr中
  15. for (int j = 0; j < arr.length; j++) {
  16. arr[j]=sc.nextInt();
  17. }
  18. //对数组arr进行排序
  19. Arrays.sort(arr);
  20. //循环处理数组arr
  21. for (int i = 0; i < arr.length-1; i++) {
  22. //将arr[i]和arr[i+1]相加并存入arr[i+1]中
  23. arr[i+1]=arr[i]+arr[i+1];
  24. //将arr[i+1]累加到number中
  25. number+=arr[i+1];
  26. //将arr[i]赋值为0
  27. arr[i]=0;
  28. //对数组arr进行排序
  29. Arrays.sort(arr);
  30. }
  31. //输出number
  32. System.out.println(number);
  33. }
  34. }

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官方认证教材》

文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树首页概览43944 人正在系统学习中
商务合作/学习交流/联系我
微信名片