貪心算法的C語言實現(xiàn)與運用詳解
貪心算法
所謂貪心算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。
貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。貪心算法的基本思路如下：
1.建立數(shù)學模型來描述問題。
2.把求解的問題分成若干個子問題。
3.對每一子問題求解，得到子問題的局部最優(yōu)解。
4.把子問題的解局部最優(yōu)解合成原來解問題的一個解。
實現(xiàn)該算法的過程：
從問題的某一初始解出發(fā)；
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]);
}
}
}
例題
題目描述：
又到畢業(yè)季，很多大公司來學校招聘，招聘會分散在不同時間段，小明想知道自己最多能完整的參加多少個招聘會(參加一個招聘會的時候不能中斷或離開)。
輸入：
第一行n，有n個招聘會，接下來n行每行兩個整數(shù)表示起止時間，由從招聘會第一天0點開始的小時數(shù)表示。
n <= 1000 。
輸出：
最多參加的招聘會個數(shù)。
樣例輸入：
3
9 10
10 20
8 15
樣例輸出：
2
活動選擇問題
概述
這個問題是對幾個相互競爭的招聘會活動進行調度，它們都要求以獨占的方式使用某一公共資源（小明）。調度的目標是找出一個最大的相互兼容的活動集合。這里是有一個需要使用某一資源（小明）的n個活動組成的集合S={a1,a2,...,an}.該資源一次只能被一個活動占用。每個活動ai有開始時間si和結束時間fi，且0<=si<fi<無窮。一旦被選擇后，活動ai就占據(jù)了區(qū)間[si,fi].如果區(qū)間[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
****************************************************************/
相關文章
這篇文章主要為大家詳細介紹了C語言實現(xiàn)設備管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
這篇文章主要為大家詳細介紹了C語言的輸入和輸出，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要為大家詳細介紹了C語言的變量和常量，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
這篇文章主要介紹了C++ 如何將string轉換成全小寫問題，具有很好的參考價值，希望對大家有所幫助。2022-11-11
這篇文章主要介紹了C語言中快速排序和插入排序優(yōu)化的實現(xiàn),包括雙向劃分快速排序方法的介紹,需要的朋友可以參考下2015-11-11
這篇文章主要為大家詳細介紹了OpenCV相機標定的相關資料，即獲得相機參數(shù)的過程，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
在此記錄一下c調用匯編的方法，匯編使用的是AT&T語法。例子很簡單，就是在給一個整數(shù)用匯編轉換成二進制2013-11-11
C++中sln,vcxproj,vcxproj.filters,lib,dll,exe的含義說明
這篇文章主要介紹了C++中sln,vcxproj,vcxproj.filters,lib,dll,exe的含義說明,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-05-05
C語言中字符串和數(shù)字的相互轉換實現(xiàn)代碼
以下是對C語言中字符串和數(shù)字的相互轉換實現(xiàn)代碼進行了分析介紹，需要的朋友可以參考下2013-07-07
UDP數(shù)據(jù)報協(xié)議是一個面向無連接的傳輸層報文協(xié)議,它簡單易用,不存在?TCP協(xié)議“粘包”的問題,下面我們就來看看如何使用qt簡單實現(xiàn)UDP通訊吧2024-04-04