1【百度之星】基础算法讲解—穷举、贪心(下)

简介: 1【百度之星】基础算法讲解—穷举、贪心(下)

贪心算法概述


贪心算法


       有一艘大船准备用来装载货物。所有待装货物都装在货箱中且所有货箱的大小都一样,但货箱的重量都各不相同。设第i个货箱的重量为wi(1≤i≤n),而货船的最大载重量为c,我们的目的是在货船上装入最多的货物。这个问题可以作为最优化问题进行描述:设存在一-组变量xi ,其可能取值为0或1。如xi为0,则货箱i将不被装上船;如xi为1,则货箱i将被装.上船。我们的目的是找到一-组xi,使它满足限制条件ni =Zwixi≤c且xi∈[0, 1], 1≤i≤n。相应的优化函数是ni= Zwixi取极值。满足限制条件的每一-组xi都是一 个可行解,能使ni= Zwixi取得极大值的方案是最优解。

       贪心算法(也称贪心策略)总是作出在当前看来是最好的选择。但我们看到,可以用动态规划算法来解,其实用贪心算法更简单,更直接且解题效率更高。这利用了问题本身的--些特性。

       对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为:首先考察问题的一个整体最优解,并证明可修改这个最优解,使其以贪心选择开始。做了贪心选择后,原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择,最终可得到问题的整体最优解。其中,证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。(当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。)


贪心算法的基本思想


贪心算法的基本思想是通过一系列选择步骤来构造问题的解,

每一步都是对当前部分解的一个扩展,直至获得问题的完整解。

所做的每一-步选择都必须满足:

(1) 可行的:必须满足问题的约束。

(2)局部最优:当前所有可能的选择中最佳的局部选择。

(3)不可取消:选择一旦做出, 在后面的步骤中就无法改变了。


例1 删数字问题.


对给定的n位高精度正整数,去掉其中k(k<n)个数字后,按原左右次序将组成一个新的正整数,使得剩下的数字组成的新数最大。

➢操作对象是一个可以超过有效数字位数的n位高精度数,存储在数组a中。

➢每次删除--个数字,选择一个使剩下的数最大的数字作为删除对象。之所以选

择这样“贪心”的操作,是因为删k个数字的全局最优解包含了删一个数字的子

问题的最优解。

➢当k>1(当然小于n),按上述操作一个一个删除。删除一个达到最大后, 再从头

即从串首开始,删除第2个,依此分解为k次完成。

➢若删除不到k个后已无左边小于右边的增序,则停止删除操作,打印剩下串的

左边n-k个数字即可(相当于删除了若干个最右边的数字)。

代码实现


1. #include<stdio.h>
2. 
3. void panduan(char* p, int k)
4. {
5. 
6.  while (k--)
7.  {
8.    char* s1 = p;
9.    while (1)//删除一个数
10.     {
11.       if (*(s1)-*(s1 + 1) < 0)
12.       {
13.         char* s2 = s1;
14.         while (*s2)
15.         {
16.           *(s2) = *(s2 + 1);
17.           s2++;
18.         }
19.         break;
20.       }
21.       s1++;
22.       if (!(*s1))//遍历结束后发现最后一位最小
23.       {
24.         *(s1 - 1) = *s1;//覆盖最后一位
25.         break;
26.       }
27.     }
28.   }
29. }
30. 
31. int main()
32. {
33.   char arr[100];
34.   int k = 0;
35.   printf("请输入要删除的数->");
36.   scanf("%s", arr);
37.   printf("请选择需要删除的位数->");
38.   scanf("%d", &k);
39.   panduan(arr, k);
40.   printf("%s", arr);
41.   return 0;
42. }

结果展示




例二 背包问题


➢已知n种物品和一一个可容纳c重量的背包,物品的重量为wi,产生的效益为pi。装包

时物品可拆,即可只装每种物品的一部分。显然物品的一部分放入背包可产生的效益为

pi/wi,问如何装包,使所得整体效益最大。

➢(1)算法设计

➢应用贪心算法求解。每一种物品装包,由可以整个装入,也可以只装一部分, 也可以不

装。

➢约束条件:目标函数:要使整体效益即目标函数最大,按单位重量的效益非增次序- -件

件物品装包,直至某-件物品装不下时,装这种物品的一部分把包装满。

示例如下:

代码实现


输入模块


1. printf("请输入物品数->");
2.  scanf("%d", &n);
3.  printf("请输入背包容量->");
4.  scanf("%f", &c);
5.  printf("请输入每个物品的重量和价值\n");
6.  while (n--)
7.  {
8.    scanf("%f%f", &wi[i], &pi[i]);
9.    i++;
10.   }

每件物品的单位价值


1. void danjia(float pj[100], float wi[100], float pi[100], int n)
2. {
3.  int i = 0;
4.  for (i = 0; i < n; i++)
5.  {
6.    pj[i] = pi[i] / wi[i];
7.  }
8. }

排序模块


以单位价值进行比较,按降序排列;并且将每个单位价值所对应重量与价值进行排序

1. void paixu(float* p, float* wi, float* pi, int n)
2. {
3.  int i = 0;
4.  for (i = 0; i < n; i++)
5.  {
6.    int j = 0;
7.    for (j = 0; j < n - 1 - i; j++)
8.    {
9.      if (*(p + j) < *(p + j + 1))
10.       {
11.         float con = *(p + j);
12.         *(p + j) = *(p + j + 1);
13.         *(p + j + 1) = con;
14.         con = *(wi + j);
15.         *(wi + j) = *(wi + j + 1);
16.         *(wi + j + 1) = con;
17.         con = *(pi + j);
18.         *(pi + j) = *(pi + j + 1);
19.         *(pi + j + 1) = con;
20.       }
21.     }
22.   }
23. }

装包模块

装包需要进行相应判断,判断是否可以全部装入;并做出判断后的相应操作

1. void zhuangbao(float* pj, float* wi, float* pi, int n, int c)
2. {
3.  int i = 0;
4.  int h = 0;
5.  float b = 0;
6.  int j = 0;
7.  int coun = 0;
8.  for (i = 0; (i < n)&&(h < c); i++)
9.  {
10.     h = h + *(wi + i);
11.   }
12.   if (h > c)
13.   {
14.     h = h - *(wi + i);
15.     b = (c - h) / *(pj + i);
16.     coun = 1;
17.   }
18.   for (j = 0; j < i-1; j++)
19.   {
20.     printf("重量为%.2f价值为%.2f  全装\n", *(wi + j), *(pi + j));
21.   }
22.   if (coun)
23.   {
24.     printf("重量为%.2f价值为%.2f  装%.2f\n", *(wi + j), *(pi + j), b);
25.   }
26. }

完整代码实现

1. #include <stdio.h>
2. 
3. void zhuangbao(float* pj, float* wi, float* pi, int n, int c)
4. {
5.  int i = 0;
6.  int h = 0;
7.  float b = 0;
8.  int j = 0;
9.  int coun = 0;
10.   for (i = 0; (i < n)&&(h < c); i++)
11.   {
12.     h = h + *(wi + i);
13.   }
14.   if (h > c)
15.   {
16.     h = h - *(wi + i);
17.     b = (c - h) / *(pj + i);
18.     coun = 1;
19.   }
20.   for (j = 0; j < i-1; j++)
21.   {
22.     printf("重量为%.2f价值为%.2f  全装\n", *(wi + j), *(pi + j));
23.   }
24.   if (coun)
25.   {
26.     printf("重量为%.2f价值为%.2f  装%.2f\n", *(wi + j), *(pi + j), b);
27.   }
28. }
29. 
30. void paixu(float* p, float* wi, float* pi, int n)
31. {
32.   int i = 0;
33.   for (i = 0; i < n; i++)
34.   {
35.     int j = 0;
36.     for (j = 0; j < n - 1 - i; j++)
37.     {
38.       if (*(p + j) < *(p + j + 1))
39.       {
40.         float con = *(p + j);
41.         *(p + j) = *(p + j + 1);
42.         *(p + j + 1) = con;
43.         con = *(wi + j);
44.         *(wi + j) = *(wi + j + 1);
45.         *(wi + j + 1) = con;
46.         con = *(pi + j);
47.         *(pi + j) = *(pi + j + 1);
48.         *(pi + j + 1) = con;
49.       }
50.     }
51.   }
52. }
53. 
54. void danjia(float pj[100], float wi[100], float pi[100], int n)
55. {
56.   int i = 0;
57.   for (i = 0; i < n; i++)
58.   {
59.     pj[i] = pi[i] / wi[i];
60.   }
61. }
62. 
63. int main()
64. {
65.   int n = 0;
66.   float c = 0;
67.   int i = 0;
68.   float wi[100];
69.   float pi[100];
70.   float pj[100];
71.   printf("请输入物品数->");
72.   scanf("%d", &n);
73.   printf("请输入背包容量->");
74.   scanf("%f", &c);
75.   printf("请输入每个物品的重量和价值\n");
76.   while (n--)
77.   {
78.     scanf("%f%f", &wi[i], &pi[i]);
79.     i++;
80.   }
81.   danjia(pj, wi, pi, i);
82.   paixu(pj, wi, pi, i);
83.   zhuangbao(pj, wi, pi, i, c);
84. 
85.   return 0;
86. }


练习


练习一 快乐司机

输入输出格式


练习二 排队打水问题


输入与输出样例


练习三 盾神与积木游戏


输入与输出格式

这些练习博主就不带大家做了,大家可以根据自己的实际情况进行适度练习。


总结


博主也是第一次参加这种比赛,博文所讲内容为博主参加学校培训所学和博主自己的一些感悟,有讲解不到位或者有错误的地方,欢迎在评论区留言或者私信博主,关于练习题的代码,也可以私信博主,但是我还是希望大家可以自己动手试一试;如果看到这里,就请给博主一个三连吧!

相关文章
|
7月前
|
算法
【软件设计师】常见的算法设计方法——穷举搜索法
【软件设计师】常见的算法设计方法——穷举搜索法
|
7月前
|
算法
枚举算法:解决问题的穷举之道(二)
枚举算法:解决问题的穷举之道(二)
|
7月前
|
算法
枚举算法:解决问题的穷举之道(一)
枚举算法:解决问题的穷举之道(一)
|
存储 算法 搜索推荐
1【百度之星】基础算法讲解—穷举、贪心(上)
1【百度之星】基础算法讲解—穷举、贪心(上)
|
算法
基础算法练习200题08、百鸡问题(循环+逻辑判断+穷举)
基础算法练习200题08、百鸡问题(循环+逻辑判断+穷举)
133 0
基础算法练习200题08、百鸡问题(循环+逻辑判断+穷举)
|
19天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
|
25天前
|
机器学习/深度学习 算法 Serverless
基于WOA-SVM的乳腺癌数据分类识别算法matlab仿真,对比BP神经网络和SVM
本项目利用鲸鱼优化算法(WOA)优化支持向量机(SVM)参数,针对乳腺癌早期诊断问题,通过MATLAB 2022a实现。核心代码包括参数初始化、目标函数计算、位置更新等步骤,并附有详细中文注释及操作视频。实验结果显示,WOA-SVM在提高分类精度和泛化能力方面表现出色,为乳腺癌的早期诊断提供了有效的技术支持。
|
5天前
|
供应链 算法 调度
排队算法的matlab仿真,带GUI界面
该程序使用MATLAB 2022A版本实现排队算法的仿真,并带有GUI界面。程序支持单队列单服务台、单队列多服务台和多队列多服务台三种排队方式。核心函数`func_mms2`通过模拟到达时间和服务时间,计算阻塞率和利用率。排队论研究系统中顾客和服务台的交互行为,广泛应用于通信网络、生产调度和服务行业等领域,旨在优化系统性能,减少等待时间,提高资源利用率。
|
13天前
|
存储 算法
基于HMM隐马尔可夫模型的金融数据预测算法matlab仿真
本项目基于HMM模型实现金融数据预测,包括模型训练与预测两部分。在MATLAB2022A上运行,通过计算状态转移和观测概率预测未来值,并绘制了预测值、真实值及预测误差的对比图。HMM模型适用于金融市场的时间序列分析,能够有效捕捉隐藏状态及其转换规律,为金融预测提供有力工具。
|
21天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。