❶ c語言演算法，用貪心法
貪心演算法雖然不是最好的，但畢竟是你要求的。。。
隨機取一個人，
循環開始：隨機取一個沒接水的人，
比較兩個人的接水時間大小，讓小的先接。
累加總等待時間為接水時間。
循環體結束。
輸出平均接水等待時間累加T/人數n
❷ 求C語言或c++的貪心演算法的例題
比如：
int a=3,b=4,c;
c=a+++b;
將被解釋為
c=(a++)+b;
而不會被解釋為
c=a+(++b);
貪心演算法的主要意義是從左至右依次解釋最多的符號！
❸ 關於一道C語言的背包問題，用的是貪心演算法
#include "iostream.h"
#include "stdio.h"
#include <cstdlib>
struct stone
{
int name;
int weight;//物品的剩餘重量
int weight_t;//物品的重量
float benefit;//物品的價值
//float b;
};
//按物品的效益排序
void sort(stone *data,int num)
{
//僅剩一個元素時排序完畢
if(num<1)
return;
int low=0,high=num;
stone key_s=data[low];//取數組的第一個作為關鍵字
float key=(float)key_s.benefit/key_s.weight;
int empty=low;//目標位置初始位置為low指向的位置
while(low<high)
{
if(low==empty)//後面的指針向前走
{
//找到比關鍵字小的元素把它移到low指向的位置
while((data[high].benefit/data[high].weight<key)&&(high>low))
{
high--;
}
if(data[high].benefit/data[high].weight>=key)
{
data[low]=data[high];
empty=high;
}
}
else if(high==empty)//前面的指針向後走
{
//找到比關鍵字大的元素把它移到high指向的位置
while((data[low].benefit/data[low].weight>=key)&&(low<high))
{
low++;
}
if(data[low].benefit/data[low].weight<key)
{
data[high]=data[low];
empty=low;
}
}
}
data[empty]=key_s;//把關鍵字放到劃分完畢後兩部分的中間位置
//關鍵字前面的數列繼續遞推
if(empty>1)
sort(data,empty-1);
//關鍵字後面的數列繼續遞推
if(num-empty-1>0)
sort(data+empty+1,num-empty-1);
}
//輸入物品的信息
void inputstone(stone *bag,int num)
{
for(int i=0;i<num;i++)
{
bag[i].name=i+1;//物品的名字
printf("請輸入第%d號物品的重量:",i+1);
scanf("%d",&bag[i].weight);
if (bag[i].weight<=0)
{printf("物品的重量必須大於0!\n");}
printf("請輸入第%d號物品的價值:",i+1);
scanf("%f",bag[i].benefit);
if (bag[i].benefit<=0)
{printf("物品的價值必須大於0!\n");}
bag[i].weight_t=bag[i].weight;
}
}
//主函數
int main(int argc, char* argv[])
{ int i;
int num=0;//放入物品的數量
int weight=0;//背包可容納的重量
float benefit=0;//總效益
stone *bag;//物品
/////輸入背包可容納的重量
do
{
printf("請輸入背包可容納的重量:");
scanf("%d",&weight);
if (weight<=0)
printf("背包可容納的重量必須大於0!\n");
}while(weight<=0);
//輸入物品種類
do
{
printf("請輸入物品的數量:");
scanf("%d",&num);
if (num<=0)
printf("物品數量必須大於0!\n");
}while(num<=0);
bag=new stone[num];//物品數組
inputstone(bag,num);//輸入物品的信息
sort(bag,num-1);//按單位效益排序
for(i=0;i<num&&weight>0;i++)
{
stone *temp=bag+i;
if(weight>=temp->weight)
{
weight-=temp->weight;
temp->weight=0;
benefit+=temp->benefit;
continue;
}
else
{
temp->weight-=weight;
weight=0;
benefit+=(temp->benefit*(1-(float)temp->weight/temp->weight_t));
break;
}
}
////////輸出結果//////////
printf("物品種類 放入的比例 每單位效益 ");
for(i=0;i<num;i++)
{
stone *temp=bag+i;
printf("%d類物品",temp->name);
printf("\t\t%.2f\t\t",(temp->weight_t-temp->weight)/(float)temp->weight_t);
printf(" %.4f\n",temp->benefit/(float)temp->weight_t);
}
printf("總效益:%.2f",benefit);
delete bag;
getchar();
system("PAUSE");
return EXIT_SUCCESS;
return 0;
}
❹ C語言貪心演算法的問題
#include <stdio.h>
#define n 7 //有多少個物品種類
struct goods //定義物品的各個屬性
{
int x; //物品放入背包的重量
int order; //物品編號
int p; //物品總價值
int w; //物品總重量
};
int Strategy1(struct goods goods[],int m) //策略一：按物品重量降序裝包
{
struct goods temp;
float value=0;
int i,j,k=0;
for(i=0;i<n-1;i++) //按照物品總價值降序排列（上面不是說要按重量排序嗎？n怎麼沒定義？）
{
for(j=i+1;j<n;j++)
{
if(goods[j].p>goods[i].p)
{
temp=goods[i];
goods[i]=goods[j];
goods[j]=temp;
}
}
}
for(;k<n;k++) //開始裝包
{
if(goods[k].w>m)
break;
goods[k].x=goods[k].w;
m-=goods[k].w; //（看程序m應該是重量限制吧！前三個裝包已經超重了，第四個當然 就沒法裝包了啊）
value+=goods[k].p;
}
if(k<n)
{
goods[k].x=m;
value=((float)m/goods[k].w)*goods[k].p;
}
printf("這是策略一的結果:\n"); //輸出結果
for(i=0;i<n;i++)
{
printf("商品%d有%f放入背包\n",goods[i].order,(float)(goods[i].x/goods[i].w));
}
printf("商品的總價值為%f",value);
return value;
}
void main()
{
float value1;
struct goods goods[7]={0,1,10,2,0,2,5,3,0,3,15,5,0,4,7,7,0,5,6,1,0,6,18,4,0,7,3,1};
int m=15;
value1=Strategy1(goods,m);
❺ 5. 設有n個顧客同時等待一項服務。顧客i需要的服務時間為ti，1<=i<=n。應如何安排n個顧客的服務次序才能
上面的 思路不錯
最優服務次序問題
一、問題描述：
設有n 個顧客同時等待一項服務。顧客i需要的服務時間為ti, 1≦i ≦n 。共有s處可以提供此服務。應如何安排n個顧客的服務次序才能使平均等待時間達到最小?平均等待時間是n 個顧客等待服務時間的總和除以n。
二、貪心選擇策略
假設原問題為T，而我們已經知道了某個最優服務系列，即最優解為A={t(1)，t(2)，…．t(n)}(其中t(i)為第i個用戶需要的服務時間)，則每個用戶等待時間為：
T(1)=t(1)；T(2)=t(1)+t(2)；...T(n)：t(1)+t(2)+t(3)+……t(n)；
那麼總等待時問，即最優值為：
TA=n*t(1)+(n-1)*t(2)+…+(n+1-j)*t(i)+…2*t(n-1)+t(n)；
由於平均等待時間是n個顧客等待時間的總和除以n，故本題實際上就是求使顧客等待時間的總和最小的服務次序。
本問題採用貪心演算法求解，貪心策略如下：對服務時間最短的顧客先服務的貪心選擇策略。首先對需要服務時間最短的顧客進行服務，即做完第一次選擇後，原問題T變成了需對n-1個顧客服務的新問題T』。新問題和原問題相同，只是問題規模由n減小為n-1。基於此種選擇策略，對新問題T』，選擇n-1顧客中選擇服務時間最短的先進行服務，如此進行下去，直至所有服務都完成為止 。
三、問題的貪心選擇性質
先來證明該問題具有貪心選擇性質，即最優服務A中t(1)滿足條件：t(1)<=t(i)(2<i<n)。
用反證法來證明：假設t(1)不是最小的，不妨設t(1)>t(i)(i>1)。
設另一服務序列B=（t(i)，t(2)，…，t(1)…，t(n)）
那麼TA-TB=n*[t(1)-t(i)]+(n+1-i)[t(i)-t(1)]=(1-i)*[t(i)-t(1)]>0
即TA>TB，這與A是最優服務相矛盾。
故最優服務次序問題滿足貪心選擇性質。
四、問題的最優子結構性質
在進行了貪心選擇後，原問題T就變成了如何安排剩餘的n-1個顧客的服務次序的問題T』，是原問題的子問題。
若A是原問題T的最優解，則A』={t(2)，…t(i)…t(n))是服務次序問題子問題T』的最優解。
證明：假設A』不是子問題T』的最優解，其子問題的最優解為B』，則有TB』<TA』，而根據TA的定義知，TA』十t(1)=TA。因此TB』+t(1)<TA』+t(1)=TA，即存在一個比最優值TA更短的總等待時間，而這與TA為問題T的最優值相矛盾。因此，A』是子問題T』的最優值。
從以上貪心選擇及最優子結構性質的證明，可知對最優服務次序問題用貪心演算法可求得最優解。
根據以上證明，最優服務次序問題可以用最短服務時間優先的貪心選擇可以達到最優解。故只需對所有服務先按服務時間從小到大進行排序，然後按照排序結果依次進行服務即可。平均等待時間即為TA/n。
五、演算法實現
由多處最優服務次序問題具有貪心選擇性質和最優子結構性質，容易證明演算法greedy的正確性。本演算法採用最短服務時間優先的貪心策略。首先將每個顧客所需要的服務時間從小到大排序。然後申請2個數組：st[]是服務數組，st[j]為第j個隊列上的某一個顧客的等待時間；su[]是求和數組，su[j]的值為第j個隊列上所有顧客的等待時間；
double greedy(vector<int>x,int s)
{
vector<int>st(s+1,0);
vector<int>su(s+1,0);
int n=x.size();
sort(x.begin(),x.end());
int i=0,j=0;
while(i<n){
st[j]+=x[i];
su[j]+=st[j];
i++;
j++;
if(j==s)j=0;//循環分配顧客到每一個服務點上
}
double t=0;
for(i=0;i<s;i++) t+=su[i];
t/=n;
return t;
}
六、演算法測試結果
七、演算法復雜性分析
程序主要是花費在對各顧客所需服務時間的排序和貪心演算法，即計算平均服務時間上面。其中，貪心演算法部分只有一重循環影響時間復雜度，其時間復雜度為O(n)：而排序演算法的時間復雜度為O(nlogn)。因此，綜合來看演算法的時間復雜度為O(nlogn)。
八、參考文獻
[1] 王曉東.計算機演算法設計與分析(第3版)[M]．北京：電子工業出版社,2007．
[2] 陳媛.《演算法與數據結構》[M],清華大學出版社, 第1版,2005.4.
[3] 王曉東.演算法設計與實驗題解 [M]．北京：電子工業出版社,2008．
附錄（程序代碼）
#include<iostream>
#include <vector>
#include<algorithm>
using namespace std;
using std::vector;
double greedy(vector<int>x,int s)
{
vector<int>st(s+1,0);
vector<int>su(s+1,0);
int n=x.size();
sort(x.begin(),x.end());
int i=0,j=0;
while(i<n){
st[j]+=x[i];
su[j]+=st[j];
i++;
j++;
if(j==s)j=0;
}
double t=0;
for(i=0;i<s;i++) t+=su[i];
t/=n;
return t;
}
void main()
{int n;//等待服務的顧客人數
int s;//服務點的個數
int i;
int a;
int t;//平均服務時間
vector<int>x;
cout<<"please input the num of the customer:"<<endl;
cin>>n;
cout<<"please input the num of the server:"<<endl;
cin>>s;
cout<<"please input the need service time of each customer:"<<endl;
for(i=1;i<=n;i++){
cout<<"No."<<i<<endl;
cin>>a;
x.push_back(a);
}
t=greedy(x, s);
cout<<"the least average waiting time is:"<<t<<endl;
}
❻ 誰能詳細講下c語言中的貪心演算法
http://wenku..com/link?url=-DpFntm7s9DmHv0s1sMHJ7Av3x3r-kA4-glj1D_-7nNr0zGNuP5Q6_ipSCLDppkm3WbUry
❼ C語言關於貪心演算法的（很簡單）
LZ在開始研究ACM嘛？
#include<stdio.h>
int least_num_cash(int _money)
{
/*直接貪心，能用大張的鈔票盡量用大張的*/
int ret=0;
while(_money!=0)
{
if(_money>=100)
{
_money-=100;
}
else if(_money>=50)
{
_money-=50;
}
else if(_money>=20)
{
_money-=20;
}
else if(_money>=10)
{
_money-=10;
}
else if(_money>=5)
{
_money-=5;
}
else if(_money>=2)
{
_money-=2;
}
else if(_money>=1)
{
_money-=1;
}
ret++;
}
return ret;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
printf("%d\n",least_num_cash(m-n));
}
return 0;
}
❽ 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;
}
❾ c語言問題急！！！（用貪心演算法）
題分析：
根據常識，我們到店裡買東西找錢時，老闆總是先給我們最大面值的，要是不夠再找面值小一點的，直到找滿為止。如果老闆都給你找分數的或者幾角的，那你肯定不幹，另外，他也可能沒有那麼多零碎的錢給你找。其實這就是一個典型的貪心選擇問題。
問題的演算法設計與實現：
先舉個例子，假如老闆要找給我99分錢，他有上面的面值分別為25，10，5，1的硬幣數，為了找給我最少的硬幣數，那麼他是不是該這樣找呢，先看看該找多少個25分的，誒99／25＝3，好像是3個，要是4個的話，我們還得再給老闆一個1分的，我不幹，那麼老闆只能給我3個25分的拉，由於還少給我24，所以還得給我2個10分的和4個1分。
具體實現
Code:
//找零錢演算法//By falcon//輸入：數組m，依次存放從大到小排列的面值數，n為需要找的錢數，單位全部為分//輸出：數組num，對照數組m中的面值存放不同面值的硬幣的個數，就找錢方案 public static int[] zhaoqian(int m[],int n) { int k=m.length; int[] num=new int[k]; for(int i=0;i<k;i++) { num<i>=n/m<i>; n=n%m<i>; } return num; }
[Ctrl+A Select All]
演示代碼
Code:
public class zhaoqian{ public static void main(String[] args) { int m[]={25,10,5,1}; int n=99; int[] num=new int[m.length]; num=zhaoqian(m,n); System.out.println(n+"的找錢方案："); for(int i=0;i<m.length;i++) System.out.println(num<i>+"枚"+m<i>+"面值"); } public static int[] zhaoqian(int m[],int n) { int k=m.length; int[] num=new int[k]; for(int i=0;i<k;i++) { num<i>=n/m<i>; n=n%m<i>; } return num; }}
[Ctrl+A Select All]
演示結果：
falcon@falcon:~/program/java$ javac zhaoqian.java
falcon@falcon:~/program/java$ java zhaoqian
99的找錢方案：
3枚25面值
2枚10面值
0枚5面值
4枚1面值