❶ 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面值