貪婪算法的C說話完成與應用詳解。本站提示廣大學習愛好者：（貪婪算法的C說話完成與應用詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是貪婪算法的C說話完成與應用詳解正文
貪婪算法
所謂貪婪算法是指，在對成績求解時，老是做出在以後看來是最好的選擇。也就是說，不從全體最優上加以斟酌，他所做出的僅是在某種意義上的部分最優解。
貪婪算法不是對一切成績都能獲得全體最優解，但對規模相當普遍的很多成績他能發生全體最優解或許是全體最優解的近似解。貪婪算法的根本思緒以下：
1.樹立數學模子來描寫成績。
2.把求解的成績分紅若干個子成績。
3.對每子成績求解，獲得子成績的部分最優解。
4.把子成績的解部分最優解分解本來解成績的一個解。
完成該算法的進程：
從成績的某一初始解動身；
while 能朝給定總目的進步一步
do 求出可行解的一個解元素；
由一切解元素組分解成績的一個可行解；
#include "stdio.h"
void main()
{
int act[11][3]={{1,1,4},{2,3,5},{3,0,6},{4,5,7},{6,5,9},
{7,6,10},{8,8,11},{9,8,12},{10,2,13},{11,12,14}};
greedy(act,11);
getch();
}
int greedy(int *act,int n)
{
int i,j,no;
j=0;
printf("Selected activities:/n");
no=0;
printf("Act.%2d: Start time %3d, finish time %3d/n", act[no],act[no+1],act[no+2]);
for(i=1;i<n;i++)
{
no=i*3;
if(act[no+1]>=act[j*3+2])
{
j=i;
printf("Act.%2d: Start time %3d, finish time %3d/n", act[no],act[no+1],act[no+2]);
}
}
}
例題
標題描寫：
又到卒業季，許多年夜公司來黉捨雇用，雇用會疏散在分歧時光段，小明想曉得本身最多能完全的加入若干個雇用會(加入一個雇用會的時刻不克不及中止或分開)。
輸出：
第一行n，有n個雇用會，接上去n行每行兩個整數表現起止時光，由從雇用會第一天0點開端的小時數表現。
n <= 1000 。
輸入：
最多加入的雇用會個數。
樣例輸出：
3
9 10
10 20
8 15
樣例輸入：
2
運動選擇成績
概述
這個成績是對幾個互相競爭的雇用會運動停止調劑，它們都請求以獨有的方法應用某一公共資本（小明）。調劑的目的是找出一個最年夜的互相兼容的運動聚集。這裡是有一個須要應用某一資本（小明）的n個運動構成的聚集S={a1,a2,...,an}.該資本一次只能被一個運動占用。每一個運動ai有開端時光si和停止時光fi，且0<=si<fi<無限。一旦被選擇後，運動ai就占領了區間[si,fi].假如區間[si,fi]和[sj,fj]互不堆疊，稱運動ai和aj是兼容的。運動選擇成績就是要選擇出一個由相互兼容的成績構成的最年夜子聚集。
將一切的運動依照停止時光升序分列
定理
關於隨意率性非空子成績Sij，設am是Sij中具有最早停止時光的運動：
fm=min{fk:ak屬於Sij}
那末，
1）運動am在Sij的某最年夜兼容運動子集中被應用
2）子成績Sim為空，所以選擇am將使子成績Smj為獨一能夠非空的子成績
ac代碼
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct join
{
int begin;
int end;
};
int compare(const void *a, const void *b);
int main()
{
int i, n, k;
struct join joins[1001], temp[1001];
while(scanf("%d", &n) != EOF)
{
for(i = 0; i < n; i ++)
{
scanf("%d %d", &joins[i].begin, &joins[i].end);
}
qsort(joins, n, sizeof(joins[0]), compare);
k = 0;
temp[k] = joins[0];
for(i = 1; i < n; i ++)
{
if(joins[i].begin >= temp[k].end)
temp[++ k] = joins[i];
}
printf("%d\n", k + 1);
}
return 0;
}
int compare(const void *a, const void *b)
{
const struct join *p = a;
const struct join *q = b;
return p->end - q->end;
}
/**************************************************************
Problem: 1463
User: wangzhengyi
Language: C
Result: Accepted
Time:10 ms
Memory:904 kb
****************************************************************/
