C++贪默算法

目次

一，定义
二，特点      
三，使用
四，步骤：
1.将问题分解为若干个问题
2.找出适合该题目标贪婪计谋
3.求解每个子问题的最优解
4.组合局部最优解
五，例题：
1，最优装载
题目分析（个人想法）：
详见代码：
2，删数问题
题目分析：
ACcode

---

一，定义

        贪默算法（greedy algorithm ）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从团体最优上加以思量，得到的是在某种意义上的局部最优解
二，特点      

  贪默算法的特点是在每一步都做出局部最优的选择，以期达到全局最优解，但并不保证能得到全局最优解。【字面意思就是每一步只看当下而不管未来。保证当下是最优解】
三，使用

因为贪默算法的特性，所以很多算法也运用到了贪婪的思想
例如之前说过的，求最短路径：dijkstra
求最小生成树的：Kruskal  prim
都是选择当前点能到达的最长（最短）的边权来举行选择，所以有些时候不是最优解。
四，步骤：

1.将问题分解为若干个问题


2.找出适合该题目标贪婪计谋


3.求解每个子问题的最优解


4.组合局部最优解

五，例题：

1，最优装载

题目分析（个人想法）：

由题目形貌可以知道，我们要寻找总价值最大的金币总和。首先就需要用价值/总质量 ，得出每单元质量下每项金币的价值。根据生活实际的惯例，在有限的空间里要尽可能地多地拿价值更高的金币，这样才气使总价值最高。因为金币可以切割，当背包空间不足时，所以我们就可以剩余的空间乘被骗前价值最高的金币的单元价值，最后将背包空间塞满，所得的物品总价值最大。
详见代码：

1. #include<bits/stdc++.h>//万能头文件。！
2. using namespace std;
3. struct node{//使用一个结构体来记录每种物品的各项信息
4.         double x,y,w;//总质量，总价值，每单位质量的价值
5.         bool operator<(const node &p) const{//重载一下运算符方便将价值排序
6.                 return w>p.w;
7.         }
8. }a[105];
9. long long read() {//日常快读压时间
10.         int x=0,f=1;
11.         char c=getchar();
12.         while(c<'0'||c>'9') {
13.                 if(c=='-') f=-1;
14.                 c=getchar();
15.         }
16.         while(c>='0'&&c<='9') {
17.                 x=x*10+c-'0';
18.                 c=getchar();
19.         }
20.         return x*f;
21. }
22. int main(){
23.         int n,m;//题目要求的n和m
24.         n=read();
25.         m=read();
26.         for(int i=1;i<=n;i++){
27.             cin>>a[i].x>>a[i].y;//输入价值和质量
28.             a[i].w=a[i].y/a[i].x;//运用公式计算出金币的单位价值
29.         }
30.         sort(a+1,a+n+1);//简单给结构体排一下序
31.         double ans=0;//建立一个变量来记录背包里的金币价值
32.         for(int i=1;m>0,i<=n;i++){
33.                 if(m>=a[i].x)ans+=a[i].y,m=m-a[i].x;//如果背包剩余空间大于目前价值最大的金币质量，直接全部放入，剩余空间减小。
34.                 else ans+=m*a[i].w,m=0;//背包空间有但还是不足的话，就用剩余空间乘上目前价值最高的金币的单位质量的价值
35.         }
36.        
37.         cout<<fixed<<setprecision(2);//按照题目要求保留两位小数
38.         cout<<ans;//输出背包价值
39. }

复制代码

2，删数问题

题目分析：

根据基本数学知识可得：当两个数数位相同的时候，高位越小，数越小，所以优先思量第i位>i+1位的第i位删除，当删干净了，就只剩0。因为是高精度数，所以使用string字符串结构更优。
ACcode

1. #include<iostream>//普通头文件
2. using namespace std;
3. int main() {
4.     string s;
5.         int k;
6.         cin>>s>>k;//先将被处理的数和处理的次数输入，
7.     while (k) {//重复k次操作。
8.             int i;
9.         for (i=0;i<s.size()-1&&s[i]<=s[i+1];i++);
10.         s.erase(i,1);
11.         k--;
12.     }
13.     if (s.empty()) {
14.         cout << 0 << endl;
15.         return 0;
16.     }
17.     int i=0;
18.     for (i=0;i<s.size()-1;) {
19.         if (s[i] =='0') i++;
20.         else break;
21.     }
22.     for(i;i<=s.size();i++){
23.             cout<<s[i];
24.         }
25.     return 0;
26. }

复制代码

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。