一、什么是贪心算法
贪心算法是一种常见的算法思想，在很多问题中都有应用。贪心算法是一种直观而且简单的算法，通过每一步选择中都采取最优的选择来达到整体最优的解。
贪心算法思路比较单一，每次选择都是当前状态下的最优选择，因此复杂度通常较低。但是，贪心算法的正确性较难证明，很多问题并不是贪心选择一定是最优解，需要对每个问题进行分析。
贪心算法用于解决那些具有最有子结构性质的问题，即问题可以分解为更小的子问题，每个子问题的最优解可以递推得到整个问题的最优解。
二、贪心算法的基本思想
贪心算法要求在每一步选择中都采取最优的选择，而得到问题的最优解。
贪心算法通常分为两个阶段：
- 建立数学模型来描述问题，找到最优解的性质；
- 利用贪心思想，每一步都做出局部最优的选择，从而达到全局最优。
贪心算法的核心是在每一步选择中都采取最优的选择，但此时必须具有无后效性。即某个状态以及之前的状态所做的选择，不会影响以后的状态。只需要考虑当前状态下的最优解，和之前的选择无关。
三、贪心算法的应用
1、背包问题
背包问题是一类经典的贪心算法问题，通常有两种类型：0/1背包问题和完全背包问题。
对于0/1背包问题，每个物品只能选一次。物品有两个限制，一个是总重量不能超过背包的最大承重，另一个是每个物品的重量和价值都不相同。贪心策略是每次选取价值比较高的物品放进背包，直到不能再加为止。这样可以获得比较好的解，但不一定是最优解。
完全背包问题中，每个物品可以选择多次放入背包中。这种问题可以转换为一个贪心问题，每次选取价值比较高的物品，直到背包无法再放下为止。
#include
using namespace std;
struct node{
int w;//重量
int v;//价值
};
int cmp(node a, node b){
return a.v > b.v;//按价值从大到小排序
}
double knapsack(node a[], int n, int m){
double ans = 0.0;
int i;
sort(a, a+n, cmp);
for(i=0; i m) break;
else{
ans += a[i].v;//先选价值最大的物品
m -= a[i].w;
}
}
if(i >n>>m;//n个物品，m为背包容量
int i;
node a[n];
for(i=0; i>a[i].w>>a[i].v;
}
printf("%.2lf", knapsack(a, n, m));
return 0;
}
2、活动选择问题
活动选择问题是一种常见的贪心算法问题，也被称为区间调度问题。该问题要求安排一个学生参加尽可能多的互不冲突的活动，以达到时间上最合理的目的。
具体实现方法是按照每个活动的结束时间从小到大排序，然后依次选择最早结束的活动，直到无法再加入为止。
#include
#include
using namespace std;
struct activity{
int start;//开始时间
int end;//结束时间
};
bool cmp(activity a, activity b){
return a.end>n;
activity a[n];
int i;
for(i=0; i>a[i].start;
cin>>a[i].end;
}
sort(a, a+n, cmp);//按结束时间从小到大排序
int cnt=1;
int last=a[0].end;
for(i=1; i=last){
cnt++;//计算可安排的活动数目
last=a[i].end;
}
}
cout<<cnt;
return 0;
}
3、霍夫曼编码
霍夫曼编码是一种使用较广泛的编码技术，主要应用于数据压缩。
在进行编码时，通常按照每个字符的出现概率从小到大排序。然后使用贪心算法构建一个霍夫曼树，来得到一组字符的编码方式，保证编码长度的最小化和解码的唯一性。
#include
#include
#include
#include
using namespace std;
struct node{
int data;//节点权值
node* left;//左子节点指针
node* right;//右子节点指针
};
struct cmp{
bool operator () (node *a, node *b){
return a->data > b->data;
}
};
string code[500];
node* root;
void preorder(node *p, string str){
if(!p) return;
if(!p->left && !p->right){
code[p->data] = str;
}
preorder(p->left, str+'0');
preorder(p->right, str+'1');
}
void build(char a[], int b[], int n){
int i;
node *left, *right;
priority_queue<node*, vector, cmp> q;
for(i=0; idata = a[i];
p->left = NULL;
p->right = NULL;
q.push(p);
}
while(q.size()>1){
left = q.top();
q.pop();
right = q.top();
q.pop();
node *p = new node;
p->data = 0;
p->left = left;
p->right = right;
p->data = left->data + right->data;
q.push(p);//构建霍夫曼树
}
root = q.top();
preorder(root, "");
}
int main(){
char a[1000];//只考虑ASCII码部分，总共只有256个字符
int b[1000];
memset(code, 0, sizeof(code));//所有编码初始化为0
int n, i;
cin>>n;
for(i=0; i>a[i]>>b[i];
}
build(a, b, n);//构建霍夫曼树
for(i=0; i<256; i++){
if(code[i]!=""){
cout<<(char)i<<" "<<code[i]<<endl;//输出字符对应的编码
}
}
return 0;
}
4、最小生成树
最小生成树是一个图的子集，可以与所有顶点相连而不形成环，并且权值之和最小。
贪心算法应用非常广泛，其中包括基于贪心策略的Prim算法和Kruskal算法。Prim算法是在新生成的最小生成树中加入一个顶点，然后找到与其相邻的最短边，将其加入最小生成树。Kruskal算法则是将所有边按照权值从小到大排序，依次加入最小生成树中，同时保证之前加入的边不会形成环。
#include
#include
using namespace std;
const int maxn = 1000;
const int inf = 0x3f3f3f;
int eg[maxn][maxn];
int vis[maxn];
int ans;
int prim(int n){
int i, j, minn;
vis[1] = 1;//从1开始遍历
for(i=1; i<n; i++){
minn = inf;
int u = -1;
for(j=1; j<=n; j++){
if(vis[j]){
for(int k=1; k<=n; k++){
if(!vis[k] && eg[j][k] >n>>m;//n个点，m条边
int i, j, x, y, w;
for(i=1; i<=n; i++){
for(j=1; j<n; j++){
eg[i][j] = inf;
}
}
for(i=0; i>x>>y>>w;//x和y之间的边权值为w
eg[x][y] = eg[y][x] = w;
}
ans = 0;
cout<<prim(n);//输出最小生成树的权值
return 0;
}
四、贪心算法的局限性
尽管贪心算法在许多问题中应用广泛，但并不是所有问题都适用于贪心思想。贪心算法求得的最优解可能并不是全局最优解。
有一些问题中，每个局部最优解可以得到全局最优。比如霍夫曼编码，贪心算法比较适用。但是对于一些问题，贪心策略可能无法达到全局最优解。比如旅行商问题，这是一个NP问题，通过贪心策略得到的最优解与全局最优解可能存在很大的误差。
因此，在处理这些问题时，需要对每个问题进行判断和分析。同时，可以通过优化贪心策略，得到比较好的局部最优解，来逐步逼近全局最优解。真正的全局最优解通常需要通过枚举或动态规划等方法得到。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/248712.html
微信扫一扫 
支付宝扫一扫 