贪心算法
一、基本概念：
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
二、贪心算法的基本思路：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
三、贪心算法适用的问题
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。
四、贪心算法的实现框架
从问题的某一初始解出发；
while （能朝给定总目标前进一步）
{
利用可行的决策，求出可行解的一个解元素；
}
由所有解元素组合成问题的一个可行解；
五、贪心策略的选择
因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。
1.最大值最小化
题目的意思就是给出ｍ个数，分成ｋ组，只能连续的分成一组。求分组中和的最大值最小。
思路：二分枚举最大值，然后划分的每一组尽量接近这个枚举的值，最大值尽量小。
这道题的核心部分是二分枚举，贪心主要体现在尽量靠近枚举的值
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 505;
long long l, r, n, group;
int a[maxn];
int vis[maxn];
bool judge(long long x) {
int k = 1, i;
long long sum = 0;
for(i=0; i<n; i++) {
if(sum + a[i] <= x) {
sum += a[i];
}else {
k++;
sum = a[i];
}
if(k>group) return false;
}
return true;
}
void print() {
memset(vis, 0, sizeof(vis));
int k = 1,i;
long long sum=0;
for(i=n-1; i>=0; i--) {
if(sum+a[i]<=l) {
sum += a[i];
}else {
k++;
sum = a[i];
vis[i] = 1;
}
}
for(i=0; i<n-1&&k<group; i++) {
if(!vis[i]) {
vis[i]=1;
k++;
}
}
for(i=0; i<n; i++) {
if(i!=n-1) {
printf("%d ", a[i]);
if(vis[i]) {
printf("/ ");
}
}
else printf("%d\n", a[i]);
}
}
int main() {
int kase;
scanf("%d", &kase);
while(kase--) {
long long sum = 0;
long long m = 0;
int i;
scanf("%d%d", &n, &group);
for(i=0; i<n; i++) {
scanf("%d", &a[i]);
sum += a[i];
m = a[i]>m?a[i]:m;
}
l=m, r=sum;
while(r>l) {
long long mid = (l+r)/2;
if(judge(mid)) {
r=mid;
}else l=mid+1;
}
print();
}
}
2.尽量少的资源消耗
有一块草坪，长为l，宽为w，在它的水平中心线上有n个位置可以安装喷水装置，各个位置上的喷水装置的覆盖范围为以它们自己的半径ri为圆。求出最少需要的喷水装置个数。
区间覆盖问题
代码：
#include<cstdio>
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 10005;
int n;
double l, w;
double p, r;
int num;
double cal() {
return sqrt(r*r-w*w/4.0);
}
struct node {
double le, ri;
bool operator<(const node& c)const {
return le<c.le;
}
}arr[maxn];
int main() {
while(scanf("%d%lf%lf", &n, &l, &w) != EOF) {
num=0;
for(int i=0; i<n; i++) {
scanf("%lf%lf", &p, &r);
if(r<=w/2) continue;
double t=cal();
arr[num].le=p-t;
arr[num].ri=p+t;
num++;
}
double le=0, ri=0;
int flag=0, ans=0;
sort(arr,arr+num);
if(arr[0].le<=0) {
int i=0;
while(i<num) {
int j=i;
while(j<num && arr[j].le<=le) {
if(ri<arr[j].ri) ri=arr[j].ri;
j++;
}
if(i==j) break;
le = ri;
i=j;
ans++;
if(ri>=l)
{
flag = 1;
break;
}
}
}
if(flag) printf("%d\n", ans);
else printf("-1\n");
}
return 0;
}
3.多机调度问题
公司要你要完成N份任务，但是你是不可能全部完成的，所以需要雇佣别人来做，做到剩下M份时，自己再亲自出马。现在有个机构，有两种付费方式，第一种是每付A元帮你完成1份，第二种是每付B元帮你完成剩下任务的一半。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 105;
char str[maxn];
int n, m, l;
struct node {
char name[maxn];
int half;
int per;
int money;
}p[maxn];
void deal (int j) {
int k = 0,i;
for (i = 0; i < strlen (str); i++) {
if (str[i] != ':')
k++;
else
break;
}
memcpy (p[j].name, str, sizeof (str));
p[j].name[k] = '\0';
int sum = 0;
for (i = k + 1; i < strlen (str); i++) {
if (str[i] != ',')
sum = sum * 10 + str[i] - '0';
else {
p[j].per = sum;
sum = 0;
}
}
p[j].half = sum;
}
void cal(int cur) {
int num = n;
int sum = 0;
while(num/2>=m && (p[cur].per*(num-num/2))>=p[cur].half) {
sum += p[cur].half;
num/=2;
}
sum += (num-m)*p[cur].per;
p[cur].money = sum;
}
int cmp (const node & x, const node & y) {
if (x.money < y.money)
return true;
else if (x.money > y.money)
return false;
else return strcmp (x.name, y.name) < 0 ? true: false;
}
int main() {
int kase;
int cas = 1;
scanf("%d", &kase);
int i, j;
while(kase--) {
printf("Case %d\n", cas++);
scanf("%d%d%d", &n, &m, &l);
getchar();
for(i=0; i<l; i++) {
gets(str);
deal(i);
cal(i);
}
sort(p, p+l, cmp);
for (j = 0; j < l ; j++)
printf ("%s %d\n", p[j].name, p[j].money);
}
return 0;
}
4.最小生成树
题目：把所有的点连起来最短
1. Kruskal
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 105;
double x[N], y[N];
struct edge {
double x, y, d;
}e[N*N];
int f[N];
double ans;
double dis(double x1, double y1, double x2, double y2) {
return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}
int n;
int num;
int cmp(edge a, edge b) {
return a.d < b.d;
}
int find(int x) {
return (x == f[x])?x:find(f[x]);
}
void uni(int a, int b) {
f[a] = find(b);
}
void ki() {
ans = 0;
for(int i=0; i<n; i++) f[i] = i;
for(int i=0; i<num; i++) {
int a = find(e[i].x);
int b = find(e[i].y);
if(a != b) {
uni(a,b);
ans += e[i].d;
}
}
printf("%.2lf\n", ans);
}
int main() {
int cas;
scanf("%d", &cas);
while(cas--) {
num = 0;
scanf("%d", &n);
for(int i=0; i<n; i++) {
scanf("%lf%lf", &x[i], &y[i]);
}
for(int i=0; i<n; i++)
for(int j=0; j<n; j++) {
if(i != j) {
e[num].x = i;
e[num].y = j;
e[num++].d = dis(x[i], y[i], x[j], y[j]);
}
}
sort(e, e+num, cmp);
ki();
if(cas) printf("\n");
}
return 0;
}
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf = 0xFFFFFFF;
double x[105], y[105], g[105][105];
int vis[105];
double d[105];
double ans;
int n;
double dis(double x1, double y1, double x2, double y2) {
return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}
void prim() {
for(int i=0; i<n; i++) d[i] = g[0][i];
d[0] = 0;
memset(vis, 0, sizeof(vis));
double m;
int x = 0;
for(int i=0; i<n; i++) {
m = inf;
for(int j=0; j<n; j++) {
if(d[j]<m && !vis[j]) {
m = d[j];
x = j;
}
}
if(m==inf) break;
ans += m;
vis[x] = 1;
for(int j=0; j<n; j++) {
if(d[j]>g[j][x] && !vis[j]) d[j] = g[j][x];//集外任意一点到已经纳入集合内的点在重调一次距离
}
}
}
int main() {
int cas;
scanf("%d", &cas);
while(cas--) {
memset(g, 0, sizeof(g));
scanf("%d", &n);
for(int i=0; i<n; i++) {
scanf("%lf %lf", &x[i], &y[i]);
}
for(int i=0; i<n; i++)
for(int j=0; j<n; j++) {
g[i][j] = dis(x[i], y[i], x[j], y[j]);
}
ans = 0;
prim();
printf("%.2lf\n", ans);
if(cas) printf("\n");
}
return 0;
}
5.最短路径
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n, m, s, d;
const int maxn = 200005;
const int inf = 0x3f3f3f3f;
struct node {
int n,w;
node(){}
node(int a,int b) {
n=a;
w=b;
}
bool operator<(const node& q)const {
return w>q.w;
}
};
vector<node>v[maxn];
int dis[maxn];
void dijkstra() {
int i;
int ans = 0;
dis[s] = 0;
priority_queue<node>q;
q.push(node(s,0));
while(!q.empty()) {
node u = q.top();
q.pop();
for(i=0; i<v[u.n].size(); i++) {
node temp = v[u.n][i];//遍历每个点
if(dis[temp.n]>dis[u.n]+temp.w) {
dis[temp.n] = dis[u.n]+temp.w;//w是从u.n到temp.n的权重
q.push(temp);
}
}
}
}
int main() {
int kase;
int t=1;
int i,j;
int a,b,c;
scanf("%d", &kase);
while(kase--) {
scanf("%d%d%d%d", &n,&m,&s,&d);
for(i=0; i<=n; i++) v[i].clear();
memset(dis, inf, sizeof(dis));
for(i=0; i<m; i++) {
scanf("%d%d%d", &a,&b,&c);
v[a].push_back(node(b,c));
v[b].push_back(node(a,c));
}
dijkstra();
printf("Case #%d: ", t++);
if (dis[d] < inf)
printf("%d\n", dis[d]);
else
printf("unreachable\n");
}
return 0;
}
京公网安备 11010502036488号