贪心算法和动态规划算法的比较 共同点： 最优子结构性质是选择类最优解都具有的性质，即全优一定包含局优 不同之处：在这里插入代码片 贪心算法具有贪心选择特性。贪心算法求得局部最优解（局部最优，不一定是全局最优） 动态规划算法从全局最优考虑问题 例一：活动安排问题 #include using namespace std;
#define NUM 50
void GreedySelector(int n, int s[], int f[], bool b[]) { b[1]=true; //默认将第一个活动先安排 int j=1; //记录最近一次加入b中的活动
//依次检查活动i是否与当前已选择的活动相容 for(int i=2;i<=n;i++) { if (s[i]>=f[j]) { b[i]=true; j=i; } else b[i]=false; } 1 }
int main() { int s[] = {0,1,3,0,5,3,5,6,8,8,2,12}; //存储活动开始时间 int f[] = {0,4,5,6,7,8,9,10,11,12,13,14}; //存储活动结束时间 bool b[NUM]; //存储被安排的活动编号 int n = (sizeof(s) / sizeof(s[0])) - 1;
GreedySelector(n, s, f, b);
for(int i = 1; i <= n; i++) //输出被安排的活动编号和它的开始时间和结束时间 { if(b[i]) cout << “活动 " << i << " :” << “(” << s[i] << “,” << f[i] << “)” <<endl; } return 0;
} 例二：0-1背包问题 #include using namespace std;
#define NUM 50
//这里假设 w[], v[] 已按要求排好序 void Knapsack(int n,float M,float v[],float w[],float x[]) { int i; for(i = 1; i <= n; i++) x[i] = 0; //初始化数组 float c = M; for(i = 1;i <= n; i++) //全部被装下的物品,且将 x[i] = 1 { if(w[i]>c) break; x[i] = 1; c -= w[i]; }
if(i <= n) x[i] = c / w[i]; //将物品i 的部分装下 1 }
int main() { float M = 50; //背包所能容纳的重量 float w[] = {0,10,20,30}; //这里给定的物品按价值降序排序 float v[] = {0,60,100,120}; float x[NUM]; //存储每个物品装入背包的比例
int n = (sizeof(w) / sizeof(w[0])) - 1;
Knapsack(n, M, v, w, x);
for(int i = 1; i <= n; i++) cout << "物品 " << i << " 装入的比例: " << x[i] << endl; return 0;
} 例三：最优装载问题 #include using namespace std;
const int N = 4;
template void Swap(Type &x,Type &y);
template void Loading(int x[], Type w[], Type c, int n);
template void SelectSort(Type w[],int *t,int n);
int main() { float c = 70; float w[] = {0,20,10,26,15};//下标从1开始 int x[N+1];
cout<<“轮船载重为：”<<c<<endl; cout<<“待装物品的重量分别为：”<<endl; for(int i=1; i<=N; i++) { cout<<w[i]<<" "; } cout<<endl; Loading(x,w,c,N);
cout<<“贪心选择结果为:”<<endl; for(int i=1; i<=N; i++) { cout<<x[i]<<" "; } cout<<endl;
return 0;
}
template void Loading(int x[],Type w[], Type c, int n) { int *t = new int [n+1];//存储排完序后w[]的原始索引 SelectSort(w, t, n);
for(int i=1; i<=n; i++) { x[i] = 0;//初始化数组x[] } for(int i=1; i<=n && w[t[i]]<=c; i++) { x[t[i]] = 1; c -= w[t[i]]; }
}
template void SelectSort(Type w[],int *t,int n) { Type tempArray[N+1],temp; memcpy(tempArray,w,(n+1)*sizeof(Type));//将w拷贝到临时数组tempArray中 int min;
for(int i=1;i<=n;i++) { t[i] = i; }
for(int i=1;i<n;i++) { min=i; for(int j=i+1;j<=n;j++) { if(tempArray[min]>tempArray[j]) { min=j; } } Swap(tempArray[i],tempArray[min]); Swap(t[i],t[min]); }
}
template void Swap(Type &x,Type &y) { Type temp = x; x = y; y = temp; } 例四：单源最短路径Kruskal算法 #include #include<stdlib.h> #include<math.h> #include #include //sort()需要用到库 using namespace std; struct point { int x; int y; int v; }; //定义结构类型，表示边 point a[9901]; //存边 int fat[101]; int n,i,j,x,m,tot,k; int father(int x){ if (fat[x] != x) fat[x] = father(fat[x]); return fat[x]; } void unionn(int x,int y){ int fa = father(x); int fb = father(y); if (fa != fb) fat[fa] = fb; } int cmp(const point &a,const point &b) { //sort()自定义的比较函数 if (a.v < b.v) return 1; else return 0; } int main(){ cin >> n; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) { cin >> x; m++; a[m].x = i; a[m].y = j; a[m].v = x; } for (i = 1; i <= n; i++) fat[i] = i; sort(a+1,a+m+1,cmp); for (i = 1; i <= m; i++) { if (father(a[i].x) != father(a[i].y)) { unionn(a[i].x,a[i].y); tot += a[i].v; k++; } if (k == n-1) break; } cout << tot; return 0; }
例五：删数问题 #include #include using namespace std; int main(){ string a; //n位数a int k; //删除数字的个数 cin>>a>>k; if (k >= a.size()) a.erase(); //如果k≥n，所有数字均被删除 else while(k > 0){ //寻找最近下降点，逐个删除 int i; for (i=0; (i<a.size()-1) && (a[i] <= a[i+1]); ++i); a.erase(i, 1);//删除xi k–; } while(a.size() > 1 && a[0] == ‘0’) //删除前导数字0 a.erase(0, 1); cout<<a<<endl; } 例六：汽车加油问题 #include using namespace std; int main(){ int n,k,i; int *station; cout<<“请输入加满一箱油的最大行驶路程和加油站的个数：”; cin>>n>>k; station=new int[k+1]; cout<<“请输入相邻的两个加油站之间的距离：”; for(i=0;i<=k;i++) cin>>station[i]; int s=0,number=0;//number记录加油的次数 s=station[0];//加满油后希望的行驶距离 for(i=1;i<=k;i++){ //i代表加油站编号 。1~7.代表将要到大的加油站 if(s>n) {cout<<“No solutin!!”; break; }//判断能否到达i加油站 else{//能到达加油站i s=s+station[i]; //到下一加油i+1站希望的 行使的距离 if(s>n){ //希望距离>n number++;//加油 s=station[i];//到下一加油站的距离 cout<<“在第”<<i<<" 个加油站加油"<<endl; } } } cout<<number<<endl; return 0; }
例七：多次服务最优问题 #include #include using namespace std; double avg(double a[],int n){
double sum=0; for(int i=0;i<n;i++){ sum+=a[i]*(n-i); } return sum/n; } int main() { double time[100]; int n; cout<<“输入排队人数”<<endl; while(cin>>n) {cout<<“分别输入”<<n<<“个人每个人的时间”<<endl; for(int i=0; i<n; i++) { cin>>time[i]; } sort(time,time+n); for(int i=0; i<n; i++) cout<<time[i]<<" "; cout<<endl; double ans=avg(time,n); cout<<ans; cout<<“输入排队人数”<<endl; } return 0; }
