會議安排c語言貪心演算法

1. 收集各類貪心演算法（C語言編程）經典題目

舉個例子,假如你買東西，老闆需要找給你99分錢，他有上面面值分別為25分，10分，5分，1分的硬幣（都是假如，不符合實際），他得找你3個25分，2個10分的，4個1分的才為最佳方案！
用貪心演算法編寫程序實現！
main()
{
int
i,a[5],b[4],c[4];
/*
define
the
type
of
the
money*/
a[1]=25;
a[2]=10;
a[3]=5;
a[4]=1;
printf("please
input
you
money
(fen):\n");
scanf("%d",&b[0]);
for
(i=1;i<=4;i++)
{
b[i]=b[i-1]%a[i];
/*take
n
25
off
and
money
left*/
c[i]=(b[i-1]-b[i])/a[i];
/*
n
*/
printf("%d
is
%d\n",a[i],c[i]);
}
getch();
}

2. C語言程序問題——活動安排問題

題目出得不嚴密，題目要求是「計算安排的活動最多時會場使用時間」，但當「安排的活動最多」有多種安排方式，題目中卻沒說輸出這多種方式中的哪一種的會場使用時間。例如 ：當有3項活動要安排，開始時間和結束時間分別是1 2、3 5、4 5，這時可以安排第一項和第二項活動，也可以安排第一項和第三項活動，前者的會場使用時間是5，後者是4，這時是輸出4還是5，題目中沒用指出。先假設測試數據不會出現上述情況，則利用貪心演算法求解活動安排問題是一種最常用的方法：#include<stdio.h>
#include<stdlib.h>
struct activity
{
int start;
int end;
}act[8501];
int comp(const void *p, const void *q)
{
struct activity *a=(struct activity *)p;
struct activity *b=(struct activity *)q;
return a->end-b->end;
}
int main()
{
int i,k,res,e;
while(scanf("%d",&k)!=EOF)
{
for(i=0;i<k;i++) scanf("%d%d",&act[i].start,&act[i].end);
qsort(act,k,sizeof(act[0]),comp);
res=act[0].end-act[0].start+1;
e=act[0].end;
for(i=1;i<k;i++)
{
if(act[i].start>e)
{
res+=act[i].end-act[i].start+1;
e=act[i].end;
}
}
printf("%d\n",res);
}
return 0;
}

3. 貪心演算法——活動安排問題

•貪心演算法的特點是每個階段所作的選擇都是局部最優的，它期望通過所作的局部最優選擇產生出一個全局最優解。

貪心與動態規劃： 與動態規劃不同的是，貪心是 鼠目寸光 ；動態規劃是 統攬全局 。

–動態規劃：每個階段產生的都是全局最優解

•第i階段的「全局」： 問題空間為(a1, … , ai)

•第i階段的「全局最優解」：問題空間為 (a1, … , ai)時的最優解

–貪心：每個階段產生的都是局部最優解

•第i階段的「局部」：問題空間為按照貪心策略中的優先順序排好序的第i個輸入ai

•第i階段的「局部最優解」： ai

•貪心選擇性質：所求問題的全局最優解可以通過一系列局部最優的選擇（即貪心選擇）來達到。

–這是貪心演算法與動態規劃演算法的主要區別。

•最優子結構性質：當原問題的最優解包含子問題的最優解時，稱此問題具有最優子結構性質。

最優子結構性質是該問題可用動態規劃演算法或貪心演算法求解的關鍵特徵

•要求高效地安排一系列爭用某一公共資源（例如會議室）的活動（使盡可能多的活動能兼容使用公共資源）。

–設有n個活動的集合E={e1,e2…en}，其中每個活動都要求使用同一資源，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi，且si<fi。如果選擇了活動i，則它在半開時間區間[si,fi)內佔用資源。

–若區間[si,fi)與區間[sj,fj)不相交，則稱ei和ej是相容的。也就是說，當si≥fj或sj≥fi時，活動i和活動j相容。

•活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合。

4. 求C語言或c++的貪心演算法的例題

比如：
int a=3,b=4,c;
c=a+++b;
將被解釋為
c=(a++)+b;
而不會被解釋為
c=a+(++b);
貪心演算法的主要意義是從左至右依次解釋最多的符號！

5. C語言，貪心演算法，貨幣找零問題

貪心演算法找零就是現實中從最大面額開始找的思路。不代表是最優解，只是演算法之一。

由於面額輸入順序不定，我先對輸入的面額進行降序排序。

下面代碼：

#include <stdio.h>

#include <malloc.h>

int main()

{

int i,j,m,n,*ns=NULL,*cn=NULL,sum=0;

printf("請輸入總金額m及零錢種類n："),scanf("%d",&m),scanf("%d",&n);

printf("請分別輸入%d種零錢的面額： ",n);

if(!(ns=(int *)malloc(sizeof(int)*n))) return 1;

if(!(cn=(int *)malloc(sizeof(int)*n))) return 1;

for(i=0;i<n;i++) scanf("%d",&ns[i]);

//------------考慮輸入面額順序不定，先對面額進行降序排列（如按照降序輸入，該段可刪除）

for(i=0;i<n;i++)

for(j=i+1;j<n;j++)

if(ns[j]>ns[i]) ns[j]^=ns[i],ns[i]^=ns[j],ns[j]^=ns[i];

//-------------------------------------------------------------------

for(i=0;i<n;i++)//貪心演算法，從最大面額開始

if(m>=ns[i])

cn[i]=m/ns[i],m=m%ns[i],sum+=cn[i],printf("%d元%d張 ",ns[i],cn[i]);

printf(" 最少使用零錢%d張 ",sum);

return 0;

}