C语言编程实例

C语言编程实例——座位调整题目描述:百度办公区里到处摆放着各种各样的零食。百度人カ资源部的调研发现,员エ如果可以在自己喜欢的美食旁边工作,工作效率会大大提髙。因此,百度决定进行一次员エ座位的大调整。调整的方法如ド:.首先将办公区按照各种零食的摆放分成N个不同的区域。(例如:可乐区，饼干区，

牛奶区等等)。.每个员エ对不同的零食区域有不同的喜好程度(喜好程度度的范围为1—100的整数，喜好程度越大表示该员エ越希望被调整到相应的零食区域)。.由于每个零食区域可以容纳的员工数量有限,人力资源部希望找到ー个最优的调整方案令到总的喜好程度最大。数据输入：第一行包含两个整数N,M,(1<=N,做=300)»分别表示N个区域和M个员エ。第二行是N个整数构成的数列a,其中a[i！表示第i个区域可以容纳的员工数,

(K=a[i]<=M,a[l]+a[2]+..+a[N]=M)〇紧接着是ー个M*N的矩阵P,P(i,j)表示第i个员エ对第j个区域的喜好度。答案输出:对于每个测试数据，输出可以达到的最大的喜好程度。输入样例33111100502510050251005025输出样例175数据解释:此数据只存在一种安排方法,三个员エ分别安置在三个区域。最终的喜好程度为100+50+25=175来源:最新评论发表评论您尚未登录本站,不能发表评论,请登录或者注册成为本站会员评论人:orichi发布时间:2013-1-915:19:50大家好,我用ruby实现了一个可以解决113的问题331111005025501085083楼下同学说:“为什么这些大牛代码的答案都是113?”但是算法还不完善，因为每个区域被选中的概率是不ー样的这个是代码地址/orichi/zuoweitiaozheng评论人:hkexiao发布时间:2012-11-1022:30:51不知道为什么有的规模大些的数据跑得反而比规模小的快如3512210056846510010054896535465264459评论人:hkexiao发布时间:2012-11-1022:00:23这个题给我的第一感觉是退火算法,但是没有用退火算法说的条件,也许用了结果会更好吧,不过不好的是代码好长,希望有高人指点ー二,在些谢谢了,呵呵!//head.hvoidaccommodate(int*(&a),intN,intM);〃实现容纳数组的赋值voidlove(int**(&L),int,int);〃实现喜好程序M*N的矩阵的输入;longanneal(int**,bool**,intN,intM);//退火算法得出最大的喜好程度bool**initia(int*a,intN,intM);〃退火算法的0・1初始化矩阵〃函数实现.cpp#include<iostream>#include<malloc.h>#include"head.h"#include<iomanip>#include<time.h>usingnamespacestd;voidaccommodate(int*(&a)JintN,intM){〃实现容纳数组的赋值;int 为当前容纳数组的和a=(int*)malloc(N*sizeof(int));if(a==NULL){coutくく”第一次内存分配失败,进行第二次内存分配”くくendl;a=(int*)malloc(N*sizeof(int));)coutくく”请输入每个区域中的工作人员数并且之和为”くくMくく”,如果不等于,系统会提示重新输入”くくendl;for(i=0;i<N;i++)*(a+i)=0;〃为容纳数组赋初值for(i=0;i<N;i++){cin>>*(a+i);if((m+=*(a+i))>M){coutくく”您当前的输入已经大于了员エ总人数”くくMくく”请重新输入”くくendl;i=0;continue;)if(i==N-l&&m<M){coutくく”您当前的输入小于员エ总人数”くくMくく”请重新输入”くくendl;i=0;continue;)})voidlove(int**(&!),intN,intM){//实现喜好程序M*N的矩阵的输入;inti,j;l=(int**)malloc(M*sizeof(int*));for(i=0;i<M;i++)*(l+i)=(int*)malloc(N*sizeof(int));coutくく”请输入',くくMくく"*"くくNくく”的喜好程序矩阵每个元素”くく”的范围为0~100如有一个不在该区间则重新输入"くくendl;for(i=0;i<M;i++)for(j=0;j<N;j++){cin>>*(*(l+i)+j);if(*(*(l+i)+j)<0II*(*(l+i)+j)>100){j=N;i=-l;coutくく"您输入的数据不在0~100内故请重新输入"くくendl;)}coutくく"您输入的喜好程度矩阵为"くくendl;for(i=0;i<M;i++){for(j=0;j<N;j++)cout<<setw(5)<<*(*(l+i)+j);cout<<endl;))bool**initia(int*a,intN,intM){〃退火算法的0-1初始化矩阵,a是岗位员工数组bool**init;inti,j,k=0;init=(bool**)malloc(M*sizeof(bool*));for(i=0;i<M;i++)*(init+i)=(bool*)malloc(N*sizeof(bool));for(i=0;i<M;i++)for(j=0;j<N;j++)*(*(init+i)+j)=0;i=0;for(j=0;j<N;j++){for(i;i<(*(a+j)+k);i++)*(*(init+i)+j)=l;k+=*(a+j);)returninit;}longanneal(int**l,bool**init,intN,intM){〃退火算法得出最大的喜好程度//I为喜好程度矩阵,a为容纳员工数数组;〃初始化0・1矩阵,每行二1,第i列的和为a[i]inti,j,rl,r2;〃做交换的两行其值不能相等longmax=0,tmp^count=0;for(i=0;i<M;i++)for(j=0;j<N;j++)if(*(*(init+i)+j)==1)max+=*(*(1+i)+j);〃初始化时的喜好程度srand(time(0));while(count<10000)(do{rl=rand()%M;r2=rand()%M;}while(rl==r2);for(j=0;j<N;j++){if(init[rl][j]==l&&init[r2][j]==0){init[rl][j]=0;init[r2][j]=l;)elseif(init[rl][j]==0&&init[r2][j]==l){init[rl][j]=l;init[r2][j]=0;tmp=0;for(i=0;i<M;i++)for(j=0;jくN;j++)if(*(*(init+i)+j)==1)tmp+=*(*(1+i)+j)；if(tmp<max)for(j=0;j<N;j++){if(init[rl][j]==l&&init[r2][j]==0){init[rl][j]=0;init[r2][j]=l;)elseif(init[rl][j]==0&&init[r2][j]==l){init[rl][j]=l;init[r2][j]=0;})else(max=tmp;count++;))cout<<n\n所得结果的0-1矩阵为"くくendl;for(i=0;i<M;i++){for(j=0;j<N;j++)cout<<setw(4)<<*(*(init+i)+j);cout<<endl;}returnmax;)//main.cpp〃本题给我的第一感觉是运用退火算法去解决#include<iostream>

#include<malloc.h>#include<iomanip>#include"head.h"usingnamespacestd;intmain(){intN,M,*a=NULL,**L=NULL"/喜好度矩阵bool**ini=NULL;〃位置矩阵longmax;〃最大满意度〃N为区域数,M为员工数,a为每个区域的员工数,长度为N,其和为Mcoutくく”请输入区域数及公司的员工数:"くくendl;cin>>N>>M;accommodate(a,N,M);love(L,N,M);ini=initia(a,N,M);max=anneal(L,ini,N,M);coutくく”最大值为:"くくmaxくくendl;return0;)写程序的时间没想到指针与引用可以结合・(&1)好奇,至少学到了评论人:zhaoxinfeng2012发布时间:2012-10-1216:00:14经过测试,所有评论者只有一个是正确的,我把测试数据留这,各位有兴趣的可以测试ー下自己的或者别人的程序:34211708050、307060、9085100、!009095。正确结果是340.评论人:zhaoxinfeng2012发布时间:2012-10-1215:06:58{评论人:kugeligui发布时间:2011-10-2314:06:17},经本人严密运算,此人公布的程序是错误的,而且,反应慢。不用谢!

评论人:395120985发布时间:2012-9-1614:27:27我有个6。行代码解决的方法评论人:TonunyLike发布时间:2012-9-1411:06:40如果存在多个最高值比如90904010010010那么这种情况选择哪个是没有影响的。评论人:jiqirenlhao发布时间:2012-9-1116:04:33考虑矩阵同时有多个相对最高值的情况了吗?评论人:TommyLike发布时间:2012-9-710:21:19个人见解,肯定还有问题,多谢指正:首先贪心算法在这里不应该是看每行的最高值,例如在矩阵中:1009080904050409020如果按照一般的来看那么100肯定属于最高的，但是这这道题里面要算的是总和的最大值，那么贪心就应该指的是每一行中相对最高的值,而不是绝对最高值,收益最高嘛，减去数组每一行的最小值那么久可以看出绝对值最高的为90TOC\o"1-5"\h\z20 10 0 -8050 0 10 -4020 70 0 -20这样第一次取出70,并根据区域的容量调整数组的位置,将舍弃的数组行（列）移至末尾，,这里已经是最后一行则不需要调整,再看容量为1,需要舍弃列，只需要调整列，将第二列移至最后，20 0 10 -8050 10 0 -4020 0 70 -20这之后再进行递归，指明现在的数组为2*2,如此直至为1*1的矩阵，这样算可以实现最优但是效率上不高，谁还有好一点的意见，求分享。voidgetMaxInterests(void)intiTempHigh=0J 〃存放最高利益//I,如果当前只剩ドー个员エ那就直接累加剩下的兴趣值if(iCurrentStaffSize==l){iMaxInterests+=stafflnterests[0][0];return;)//2(如果不是,则将兴趣区域分配的数组进行重新调整,去掉兴趣分配最低点for(inti=0;i<iStaffCounts;i++){〃,获取每ー个员エ兴趣分配的最低点并先加到Maxinterest上,保存当前位置for(intj=0;j<iZoneCounts;j++)|〃保存最低点arrayinterestsLow[i]arrayInterestsLow[i]>staffInterests[i][j]?stafflnterests[i][j]:arraylnterestsLow[i];)〃减去最低点形成新的数组for(intj=0;j<iZoneCounts;j++){stafflnterests[i][j]stafflnterests[i][j]-arrayInterestsLow[i];〃保存最高点以及位置,判定条件最高并且有容量if((iTempHigh<stafflnterests[i][j])&&arrayPerStaffInZone[j]!=0)iStaffPos=i;iZonePos=j;iTempHigh=stafflnterests[i][j];})〃先加上每个员エ的兴趣最低点iMaxInterests+=arrayInterestsLow[i];}〃获取最高值并累加iMaxInterests+=iTempHigh;〃调整数组大小iCurrentstaffSize--;if(0==--arrayPerStaffInZone[iZonePos]){iCurrentZoneSize--;)〃调整数组位置for(inti=0;i<iZoneCounts;i++){exchangeItem(staffInterests[iStaffPos][i],staffInterests[iStaffCounts-l][i]);)if(iCurrentZoneSize!=iZoneCounts){for(inti=0;i<iStaffCounts;i++){exchangeltem(staffInterests[i][iZonePos],stafflnterests[i][iZoneCounts-1]);)〃替换容量数组中容量位置exchangeitem(arrayPerStaffInZone[iZonePos],arrayPerStaffInZone[iZoneCounts-l]);iZoneCounts--;)iStaffCounts--;returngetMaxInterests();)评论人:ybnl8t发布时间:2012-6-519:58:29感觉只能穷举了,其它的都有问题评论人：宝贝赢赢发布时间：2012-5-1620:25:30有哪位大牛能有一百行的代码解决这个问题吗?评论人：paniclp发布时间:2012-4-1810:43:28这个题目其实就是8皇后问题,只不过条件变成横行和纵行不在一条线上,不用考虑斜线。利用递归回溯解决。评论人:snowlyworld发布时间:2012-3-2814:52:56staticconstintM=3;staticconstintN=3;staticintc叩ac口={1,1,1};vector<int>eraseRow(constvector<int>&v,inti,intcurrentArea){intcolSize=N-currentArea;vector<int>newVec;newVec.reserve(v.size()-colSize);newVec.insert(newVec.begin(),v.begin(),v.begin()+i*colSize);newVec.insert(newVec.end()Jv.begin()+(i+l)*colSizeJv.end());returnnewVec;}vector<int>eraseCol(constvector<int>&v,intcurrentArea){vector<int>newVec;for(inti=0；i!=v.size();++i){if(i%(N-currentArea)){newVec.push_back(v[i]);}}returnnewVec;}intgetMax(vector<int>v,intnumOfPeop,intnumOfCapac,intcurrentArea=0jintstart=0){intsum=0,max=0;intcurr=currentArea;if(numOfPeop<numOfCapac){cerr<<"thenumOfPeopleissmallerthanCapacity”くくendl;return-1;)elseif(numOfPeop==numOfCapac)for(inti=0;i!=numOfCapac;++i)max+=v[i];)else{vector<int>newVec;if(numOfCapac==1)(for(inti=0;i<=numOfPeop-numOfCapac;++i){sum=v[i*(N-cum)];newVec=eraseRow(v,i,curr);newVec=eraseCol(newVec,cum);if(cum<N){sum+= getMax(newVec, numOfPeop-1,capac[cum+1],cum+l);)max=(max>sum?max:sum);))else{if(numOfCapac<l)(cem<<"numOfCapacityissmallerthanzero”くくendl;return-1;for(inti=start;i!=numOfPeop-numOfCapac;++i)sum=v[i*(N-cum)];1,cum,i);newVec=eraseRow(v,i,curr);1,cum,i);sum+=getMax(newVecnumOfPeop-1,numOfCapac-max=(max>sum?max:sum);})}returnmax;)voidprintVec(constvector<int>&v){intdelim=1;for(inti=0;i!=v.size();++i,++delim)(cout«v[i]<<,,\t,,;if(!(delim%3))(cout<<endl;}))voidmain(intargc,char**argv){ifstreamifs("IntrestArea.txt'*);vector<int>v;v.reserve(M*N);inti;while(ifs>>i)v.push_back(i);)intmax=getMax(Vjcapac[0]);cout<<max<<endl;)评论人:宝贝赢赢发布时间:2012-3T41:25:08其实穷举倒是可以,就是极其的繁琐,我已经有了一个穷举的办法,不过就算是对于N=20的问题也计算了一百万多次,简直让人无法忍受评论人：宝贝贏赢发布时间：2012-3T41:20:14我觉得可以用背包问题做，可惜没有找到办法评论人：最爱六月发布时间：2012-3-1316:56:05楼上一派胡言你跑过你写的程序了吗?？评论人:betakoii发布时间:2012-3-1018:44:21voidsort(inta[],intbロ)〃b函数得到a函数大小排序的下标值{inti,j,max,t;〃b保存下标intlength=sizeof(a);fon(i=0;i<length-l;i++){max="l;t=0;for(j=0;j<length-l;j++){if(i==0)if(a[j]>max)

max=a[j];t=j;}}else{if(a[j]>max&&a[j]<a[b[i-l]]){max=a[j];t=j；)})b[i]=t;)}voidmain(){inti,m,n,a[100],b[100],c[100],j,total;scanf("%d%d”,&n,&m);〃n代表区m代表人for(i=0;i<n;i++){scanf("%d",&a[i])"/获得每个区的人数)total=0;for(i=0;i<m;i++)(for(j=0;j<n;j++)scanf("%d",&b[j]);

sort(b,c);for(j=0;j<n;j++)〃获取某人属于哪个区{if(a[c[j]]!=0){a[c[j]]--;printf("%d\n",b[c[j]]);total+=b[c[j]];break;)))printf("%d",total);)评论人:宝贝赢赢发布时间:2012-3-713:16:59有没有人能给个简便的算法的啊评论人:blake326发布时间:2011-12-3011:54:58想了好几天,都没有想出个好办法来。尽量的往动态规划上靠还是没有成功。只能用最土的穷举法莱解决了331111005025501085083至少这个例子能跑通,还有一个限制总座位数必须和员工数目ー样多。代码:#include<stdio.h>

intarea_nr;intemployee_nr;int*capacity_area;int**employee_favor;intseat_nr;structseat_info{intarea_id;intemployee_id;intfavor;};structseat_info*seats;inttmp_employee[100];intupdate_empty_employee(intseat_id>intempty_employee_id[100]){intempty_employee_nr;inti,j;memset(empty_employee_id)01sizeof(empty_employee_id));memset(tmp_employee>0,sizeof(tmpemployee));for(i=0;i<seat_id;i++){tmp_employee[seats[i].employee_id]=1;}for(i=0,j=0;i<employee_nr;i++){if(tmp_employee[i]==0){empty_employee_id[j++]=i;)empty_employee_nr=j;returnempty_employee_nr;)voidfunc(intseat_id){intempty_employee_id[100];intempty_employee_nr;if(seat__id==seat_nr-l){empty_employee_nr= update_empty_employee(seat_id,empty_employee_id);seats[seat_id].employee_id=empty__employee_id[0];seats[seat_id],favor =employee_favor[empty_employee_id[0]][seats[seat_id].area_id];inti;intsum_favor=0;printf(" \n“)；for(i=0;i<seat_nr;i++){printf("seat[%d],area=%d,employee=%d,favor=%d\n”,i,seats[i].area_id,seats[i]・employee_id,seats[i].favor);sum_favor+=seats[i].favor;)printf("sumfavor=%d\n",sum__favor);return;)empty_employee_nr = update_empty_emp丄oyee(seat_id,empty_employee_id);inti;for(i=0;i<empty_employee_nr;i++){seats[seat_id].employee_id=empty_employee_id[i];seats[seat_id].favor =employee_favor[seats[seat_id].employee_id][seats[seat_id].area_id];func(seat_id+l);)}intmain(intargc,char**argv){intij;printf("input:\nM);scanf("%d%d",&area_nr,&employee_nr);capacity_area=(int*)malloc(sizeof(int)*area_nr);for(i=0;i<area_nr;i++){scanf("%d”,&capacity_area[i]);)employee_favor=(int**)malloc(sizeof(int*)*employee_nr);for(i=0;i<employee_nr;i++){employee__favor[i]=(int*)malloc(sizeof(int)*area_nr);for(j=0；j<area_nr;j++){scanf("%d"J&employee_favor[i][j]);))printf("inputsuccess:\n");printf("area_nr=%d>employee_nr=%d\n”,area_nr,employee_nr);printf("areacapacity:\n");for(i=0;i<area_nr;i++){printf("%d\t'\capacity_area[i]);}printf("\n");printf("employeefavor:\n");for(i=0;i<employee_nr;i++){printf("[%d]:'i);for(j=0;j<area_nr;j++){printf("%d\t",employee_favor[i][j]);}printf("\n");}seat_nr=0;for(i=0;i<area_nr;i++){seat_nr+=capacity_area[i];)seats=(structseat_info*)malloc(seat_nr*sizeof(structseat_info*));intseat_id=0;for(i=0;i<area_nr;i++){for(j=0;j<capacity_area[i];j++){seats[seat__id].areaid=i;-1；seats[seat_id].-1；seats[seat_id].favor=-1;seat_id++;})func(0);return0;}评论人:walk_shadow发布时间:2011-11-2621:26:14331111005025501085083楼下同学说:“为什么这些大牛代码的答案都是113?”我觉得答案应该是100+8+8=116吧,对不对?呵呵,要是题意没有把握好就没法做呢评论人:bingshen发布时间:2011-11-2614:23:59难道没有人能够看出来这个是KM算法吗?评论人:sujian19900703发布时间:201171-523:22:17331111005025501085083为什么这些大牛代码的答案都是113?难道真的是我错了?评论人:shentianzhou发布时间:2011-10-2720:02:31/・争位置的思想。就是说每个人都要跟己选好的区域的人比较。比如:B虽然比A在某区域的喜好程度低了X,但B在其他区域的喜好程度比A低了Y。(XY有正负之分)则如果X・Y>0,B就可以赶走A。A继续找位置*/#include<stdio.h>#include<stdlib.h>#defineMAX300intFindNextMan(intLM,int*P)(inti;for(i=l;i<=LM;i++){if(P[i]==0)break;elsecontinue;)if(i==(LM+1))return0;elsereturni;)voidFindNextMax(intIM,intLN,int*A,int**P,int**Q){inti,k,TN,TM,TEMP,TEMP_A,TEMP_B;TN=TM=TEMP=0；for(i=l;i<=LN;i++)for(j=l；j<=A[i]；j++){TEMP_A=P[i][IM]-P[i][Q[i][j]]；TEMP_B=0;if(Q[i][j]!=0){for(k=l;k<=LN;k++)(if(i==k)continue;if(TEMP_B<(P[k][Q[i][j]]-P[k][IM])){TEMP_B=P[k][Q[i][j]]-P[k][iM]；)elsecontinue;))if(TEMP<(TEMP_A+TEMP_B))(TEMP=TEMP_A+TEMP_B；TN=i;TM=j；}})P[〇][IM]=TN;P[0][Q[TN][TM]]=0;Q[TN][TM]=IM；intmain(){FILE*INF;intN,M,i,j,SUM,*A,**P,**Q;A=(int*)malloc((MAX+l)*sizeof(int));P=(int**)malloc((MAX+l)*sizeof(int*));Q=(int**)malloc((MAX+l)*sizeof(int*));for(i=0;i<=MAX;i++){P[i]=(int*)malloc((MAX+l)*sizeof(int));Q[i]=(int*)malloc((MAX+l)*sizeof(int));}INF=fopen("input.txt","r");fscanf(INF,"%d",&N);fscanf(INF,"%d",&M);for(i=l;i<=N;i++){P[i][0]=0；fscanf(INF,"%d",&A[i]);)for(i=l;i<=M;i++)(P[0][i]=0；for(j=l;j<=N;j++)Q[j][i]=0；fscanf(INF,"%d",&P[j][i]);))fclose(INF);while(true)i=FindNextMan(M,P[0]);if(i==0)break;elseFindNextMax(i,N,A,P,Q);)SUM=0;for(i=l;i<=N;i++)(for(j=l；j<=A[i];j++){SUM+=P[i][Q[i][j]]；))printf("\n %d \n",SUM);for(i=0;i<=MAX;i++)(free(P[i]);free(Q[i]);)free(P);free(Q);free(A);return0;)评论人:kugeligui发布时间:2011-10-2314:06:17#include<stdio.h>#include<stdlib.h>typedefintelemtype;#defineLENsizeof(HoblitData)#include<malloc.h>//intB=0;typedefstructData{elemtypei,j,data;structData*next;}HoblitData;intPanduan(int*aJint*b,intMax,HoblitData*p,int*c,intM,int*B)〃判断传值过来的最大值是否有效,有效返回1,反之返回0{HoblitData*pl;inti;pl=p;while(pl->next!=NULL){pl=pl->next;if(pl->data==Max){b[pl->j]++;for(i=0;i<M;i++)if(pl->i==c[i])break;〃只有同时满足小于各个零食区域的和前面没有存放行下标オ返回1{if(i==M){*(c+*B)=pl->i;(*B)++;return1;}elseb[pl->j]--;}return0;}))intFindMax(HoblitData*p){HoblitData*pl;elemtypeMax=0;pl=p->next;while(pl!=NULL)if(pl->data>Max)Max=pl->data;pl=pl->next;)returnMax;}voidDeleteData(HoblitData*pJintMax){HoblitData*pl,*p2;P1=P；while(pl->next!=NULL){p2=pl；pl=pl->next;if(pl->data==Max){if(p2==p)p->next=pl->next;elsep2->next=pl->next;break;))voidVoluation(int*a,intN,intM)〃分配各个零食区域的员工数函数(inti;while(l){printf(“请输入%d个零食区域的各员工数:'n'，N);for(i=l;i<N+l;i++)(scanf(M%d%a+i);*a+=*(a+i);}if(*a!=M)printf(“你所输入的总员工数和实际的员工数不同、n”)；elsebreak;))HoblitData*create(intM,intN)//将第i个员エ对第j个区域的喜好度以链表的行存储形式存储起来,链表中的数据为下标和喜好度{HoblitData*p,*head;inti,j;head=(HoblitData*)malloc(LEN);head->next=NULL;printf("请输入各个员エ对各个区域的喜好度:、n");for(i=l;i<M+l;i++)for(j=l;j<N+l;j++)p=(HoblitData*)malloc(LEN);scanf("%d"J&p->data);p->i=i；P->j=j；p->next=head->next;head->next=p;}returnhead;)voidmain()(intM,N;HoblitData*head;inta[100]={0}Jb[100]={0}Jc[100]={0}JMaxJiJsum=0JB=0,*Ajk;A=&B;printf(“请输入员エ的数量:l=<M<=300\nn);scan千「%d'&M);printf(”请输入零食区域的个数:l=<N\nn);scanf("％d\&N);head二create(M'N);Voluation(a,N,M);for(i=0;i<M;i++)(Max=FindMax(head);k=Panduan(a>b>Max,head,c,M,A);if(k==l)sum+=Max;elseDeleteData(head,Max);

printf（"员エ对零食区域的总的喜好度为％Uバ切）；评论人:c519299013发布时间:2011-10-1513:41:58#include<stdio.h>#include<stdlib.h>typedefintelemtype;#defineLENsizeof(HoblitData)#include<malloc.h>//intB=0;typedefstructData{elemtypei,j,data;structData*next;}HoblitData;intPanduan(int*a,int*b,intMax,HoblitData*p,int*cintM,int*B)〃判断传值过来的最大值是否有效,有效返回1,反之返回0{HoblitData*pl;inti;pl二p;while(pl->next!=NULL)(pl=pl->next;if(pl->data==Max){b[pl->j]++;for(i=0;i<M;i++)if(pl->i==c[i])break;遅作国1-*]く=3国1->：)])〃只有同时满足小于各个零食区域的和前面没有存放行下标オ返回1{if(i==M){*(c+*B)=pl->i;(*B)++;return1;)elseb[pl->j]--;}return0;}))intFindMax(HoblitData*p){HoblitData*pl;elemtypeMax=0;pl=p->next;while(pl!=NULL){if(pl->data>Max)Max=pl->data;pl=pl->next;)returnMax;}voidDeleteData(HoblitData*pJintMax){HoblitData*pl,*p2;P1=P；while(pl->next!=NULL){p2=pl；pl=pl->next;if(pl->data==Max)|if(p2==p)p->next=pl->next;elsep2->next=pl->next;break;))}voidVoluation(int*a,intN,intM)〃分配各个零食区域的员工数函数{inti;while(l)(printf("请输入％d个零食区域的各员工数:'n'N);for(i=l;i<N+l;i++){scanf("%d'\a+i);*a+=*(a+i);)if(*a!=M)printf(“你所输入的总员工数和实际的员工数不同、ベ)；elsebreak;})HoblitData*create(intM,intN)〃将第i个员エ对第j个区域的喜好度以链表的行存储形式存储起来,链表中的数据为下标和喜好度{HoblitData*pJ*head;inti,j;head=(HoblitData*)malloc(LEN);head->next=NULL;printf(”请输入各个员エ对各个区域的喜好度:'べ)；for(i=l;i<M+l;i++)for(j=l;j<N+l;j++){p=(HoblitData*)malloc(LEN);scanf("%d"j&p->data);p->i=i;P->j=j；p->next=head->next;head->next=p;)returnhead;)voidmain(){intM,N;HoblitData*head;inta[100]={0},b[100]={0},c[100]={0}JMaxJiJsum=0>B=0J*AJk;A=&B;printf("请输入员エ的数量:：L=〈Mく=300\n")；scanf(”%d\&M);printf("请输入零食区域的个数:l=<N\nn);scanf(n%d'\&N);head=create(M,N);Voluation(a,N,M);for(i=0;i<M;i++){Max=FindMax(head);k=Panduan(a,b,Max,head,c,M,A);if(k==l)sum+=Max;elsei-SDeleteData(head,Max);）printf（"员エ对零食区域的总的喜好度为％d",sum）;评论人:wsywhong发布时间:2011-9-3017:06:46可以用贪心算法做,但得到的解不一定是最优解用常规的0-1规划法做很容易但有一个问题:时间复杂性偏高评论人:Mayer发布时间:2011-9-2723:52:42我有个办法不过循环太多...哪位同学帮忙改进ー下#include<iostream>usingnamespacestd;voidmain(){intN,M,i,j;cin>>N>>M;intcap[300];for(i=0;i<N;i++)|cin>>cap[i];}intfavour[90000];for(j=0;j++)(cin>>favour[j];)intareanum,kJh>sum=0Jmax,runtime=M;while(runtime>0){max="l;for(j=0；j++)if(favour[j]>=max)max=favour[j];k=j；})areanum=k%N;if(cap[areanum]>0){cap[areanum]sum=sum+max;for(h=k-areanum;h<=k-areanum+N-l;h++)(favour[h]=-l;)runtime--;)if(cap[areanum]==0){for(inta=0;a<N;a++)(favour[areanum+a*M]=-l;)))cout<<"theresultis:"<<""<<sum;system("pauseH);}评论人:sujian19900703发布时间:2011-9-1810:37:54这道题貌似不是贪心331111005025501085083???刚オ打快了!1评论人:sujian19900703发布时间:2011-9T810:36:31这道题貌似不是贪心3311110050255010850820???评论人:864258458发布时间:2011-9-819:38:36就是个贪心算法。。。。评论人:shadow,meng发布时间:2011-6T49:44:00#include<stdio.h>#include<memory>#defineSTAFFID(staff)(staff»16)〃员エ号#defineSTAFFFAVNUM(staff)(staff&0xFFFF)〃喜好程度#defineSETエD(staff,ID)(staff|=(ID<<16))#defineSETFAVNUM(staff,fav)(staff|=(fav&OxFFFF))voidQuickSort(intlow,inthigh,unsignedint*pMatrix){if(low<high)(intstart=low,end=high;high--;unsignedintsplitvalue=pMatrix[low];while(low<high){while(low<high&&STAFFFAVNUM(pMatrix[high]) <=STAFFFAVNUM(splitvalue))high--;pMatrix[low]=pMatrix[high];while(low<high&&STAFFFAVNUM(pMatrix[low]) >=STAFFFAVNUM(splitvalue))low++;pMatrix[high]=pMatrix[low];}pMatrix[low]=splitvalue;Quicksort(start,low,pMatrix);QuickSort(low+1,end,pMatrix);)}boolProcessinput(char*input,intnumber,unsignedint*pArray,boolisStaff=false,unsignedshortstaffID=0)charchCode;charszNumber[10];intpos=0;intwordPos=0;intiRecordCount=0;do{chCode=input[pos];if(chCode==''||chCode==*\n|||chCode==*\0*){szNumber[wordPos++]='\0';wordPos=0;if(isStaff){intstaffvalue=0;SETID(staffvalue,staffID);SETFAVNUM(staffvalue,atoi(szNumber));pArray[iRecordCount]=staffvalue;}elsepArray[iRecordCount]=atoi(szNumber);iRecordCount++;)elseif(chCode>='0'&&chCode<='9'){szNumber[wordPos++]=chCode;)elsebreak;pos++;}while(chCode!=*\n'&&chCode!='\0');if(iRecordCount!=number){returnfalse;)returntrue;}int_tmain(intargc,_TCHAR*argv[]){intn,m;unsignedinttotal=0;charszlnput[1024];unsignedintNM[4];printf("pleaseinputN,M:");gets(szlnput);if(!ProcessInput(szInput,2,NM))return-1;n=NM[0];m=NM[1];bool*bSaveFlag=(bool*)malloc(m);int*pCurrentPosFlag=(int*)malloc(n*sizeof(int));unsignedint*pAreaCapacity=(unsignedint*)malloc(n*sizeof(unsignedint));unsignedint*pMatrix=(unsignedint*)malloc(n*m*sizeof(unsignedunsignedint*pMatrix=int));unsignedint*pSectorMatrix=(unsignedint*)malloc(n*m*sizeof(unsignedint));if(!bSaveFlag||!pMatrix||!pSectorMatrix||!pCurrentPosFlag||!pAreaCapacity)return-1;gets(szlnput);if(!ProcessInput(szInput,n,pAreaCapacity))return-1;inti=0;while(i<n)]gets(szlnput);if(!Processエnput(szエnput,m,pMatrix+i*m,true,i))return-1;i++；)for(inti=0;i<n;i++)for(intj=0;j<m;j++)*(pSectorMatrix+i*m+j)=*(pMatrix+j*n+i);if(pMatrix)free(pMatrix);memset(bSaveFlag,0x0,m);*sizeof(unsignedint));memset(pCurrentPosFlag,0x0,nfor(inti=0;i<n;++i)*sizeof(unsignedint));〃按m个员エ对N个区域的喜好程序排序。一共排序n次。QuickSort(i*m,(i+1)*m,pSectorMatrix);)〃所以对应n个区域的n个队列第一个员エ始终是最大的。〃取在n个队列第一个员工中最大的那一个(只要N区未满,且没有取过的员エ),取m次就是最大组合。unsignedintsaveCount=m;do{unsignedinttempFav=0,tempID=0;;boolfirstGot=false;intindex;for(inti=0;i<n;++i){if(pCurrentPosFlag[i]<m&&pAreaCapacity[i]>0){intpos;unsignedintstaffvalue;while((pos=pCurrentPosFlag[i])<m){staffvalue=*(pSectorMatrix+i*m+pos);if(!bSaveFlag[STAFFID(staffvalue)])break;pCurrentPosFlag[i]++;}if(!firstGot){tempID=STAFFID(staffvalue);tempFav=STAFFFAVNUM(staffvalue);index=i;firstGot=true;)if(tempFav<STAFFFAVNUM(staffvalue)){tempID=STAFFID(staffvalue);tempFav=STAFFFAVNUM(staffvalue);index=i;)}}pCurrentPosFlag[index]++;pAreaCapacity[index]total+=tempFav;bSaveFlag[tempID]=true;saveCount--;}while(saveCount>0);printf(nmaxvalueis:%dM,total);if(pSectorMatrix)free(pSectorMatrix);if(bSaveFlag)free(bSaveFlag);if(pCurrentPosFlag)free(pCurrentPosFlag);if(pAreaCapacity)free(pAreaCapacity);return0;)评论人:shadow,meng发布时间:2011-6-1315:57:50#include<stdio.h>#include<memory>#defineSTAFFID(staff)(staff»16)〃员エ号#defineSTAFFFAVNUM(staff)(staff&OxFFFF)〃喜好程度#defineSETID(staff,ID)(staff|=(ID«16))#defineSETFAVNUM(staff,fav)(staff|=(fav&0xFFFF))voidQuickSort(intlow,inthigh,unsignedint*pMatrix){if(low<high){intstart=low,end=high;high--;unsignedintsplitvalue=pMatrix[low];while(low<high){while(low<high&&STAFFFAVNUM(pMatrix[high]) <=STAFFFAVNUM(splitvalue))high--;pMatrix[low]=pMatrix[high];while(low<high&&STAFFFAVNUM(pMatrix[low]) >=STAFFFAVNUM(splitvalue))low++;pMatrix[high]=pMatrix[low];}pMatrix[low]=splitvalue;Quicksort(start,low,pMatrix);QuickSort(low+1,end,pMatrix);))boolProcesslnput(char*input,intnumber,unsignedint*pArray,boolisStaff=false){charchCode;charszNumber[10];intpos=0;intwordPos=0;intiRecordCount=0;do{chCode=input[pos];if(chCode==''||chCode==1\n*||chCode==*\0'){szNumber[wordPos++]='\0';wordPos=0;if(isStaff)(intstaffvalue=0;SETID(staffvalue,iRecordCount);SETFAVNUM(staffvalue,atoi(szNumber));pArray[iRecordCount]=staffvalue;)elsepArray[iRecordCount]=atoi(szNumber);iRecordCount++;)elseif(chCode>='0'&&chCode<='9'){szNumber[wordPos++]=chCode;)elsebreak;pos++;}while(chCode!='\n'&&chCode!='\0');if(iRecordCount!=number)]returnfalse;)returntrue;)int__tmain(intargc,_TCHAR*argv[]){intn,m;unsignedinttotal=0;charszlnput[1024];printfC'pleaseinputN,M:“);gets(szlnput);if(!ProcessInput(szInput,2,NM))return-1;n=NM[0];m=NM[1];bool*bSaveFlag=(bool*)malloc(m);int*pCurrentPosFlag=(int*)malloc(n*sizeof(int));unsignedint*pAreaCapacity=(unsignedint*)malloc(n*sizeof(unsignedint));unsignedint*pMatrix=(unsignedint*)malloc(n*m*sizeof(unsignedint));unsignedint*pSectorMatrix=(unsignedint*)malloc(n*m*sizeof(unsignedint));if(!bSaveFlag||!pMatrix||!pSectorMatrix||!pCurrentPosFlag||!pAreaCapacity)return-1;gets(szlnput);if(!ProcessInput(szInput,n,pAreaCapacity))return-1;inti=0;while(i<n)(gets(szlnput);if(!Processlnput(szlnput,m,pMatrix+i*m,true))return-1;i++；for(inti=0;i<n;i++)for(intj=0;j<m;j++)*(pSectorMatrix+i*m+j)=*(pMatrix+j*n+i);if(pMatrix)free(pMatrix);memset(bSaveFlag^0x0,m);memset(pCurrentPosFlag,0x0,n*sizeof(unsignedint));for(inti=0;i<n;++i){〃按m个员エ对N个区域的喜好程序排序。一共排序n次。QuickSort(i*m,(i+1)*m,pSectorMatrix);)〃所以对应n个区域的n个队列第一个员エ始终是最大的。〃取在n个队列第一个员工中最大的那一个(只要N区未满,且没有取过的员エ),取m次就是最大组合。unsignedintsaveCount=m;do{unsignedinttempFav=0,tempID=0；;boolfirstGot=false;intindex;for(inti=0;i<n;++i){if(pCurrentPosFlag[i]<m&&pAreaCapacity[i]>0)intpos;unsignedintstaffvalue;while((pos=pCurrentPosFlag[i])<m)(staffvalue=*(pSectorMatrix+i*m+pos);if(!bSaveFlag[STAFFID(staffvalue)])break;pCurrentPosFlag[i]++;)if(IfirstGot){tempエD=STAFFID(staffvalue);tempFav=STAFFFAVNUM(staffvalue);index=i;firstGot=true;)if(tempFav<STAFFFAVNUM(staffvalue)){tempID=STAFFID(staffvalue);tempFav=STAFFFAVNUM(staffvalue);index=i;)})pCurrentPosFlag[index]++;pAreaCapacity[index]total+=tempFav;bSaveFlag[tempID]=true;saveCount--;}while(saveCount>0);printf("maxvalueis:%d'\total);if(pSectorMatrix)free(pSectorMatrix);if(bSaveFlag)free(bSaveFlag);if(pCurrentPosFlag)free(pCurrentPosFlag);if(pAreaCapacity)free(pAreaCapacity);return0;)评论人:zbhstar发布时间:2011-5-239:25:30我分析的当成了个排列题目做的,大家有感兴趣帮忙测试测试ー下评论人:zbhstar发布时间:2011-5-239:25:18我分析的当成了个排列题目做的,大家有感兴趣帮忙测试测试ー下#include<stdio.h>#include<stdlib.h>voidget_num__area(int*N);voidget_num_person(int*M);voidget_area_max(intN,int**area_max);voidget_love_matrix(intN,intM,int**love);voidswap_num(int*x,int*y);voidpai_lie(int*shu_lie,intstart,intend);voidprint_info(int*a,inti);intget_area_num(int*area_limt,intn,intseq_num);voidtest();intN;intM;int*love;int*area_max;intmax_nesult=0;intmax_nesult_temp=0;int*person_num;intmain(intargc,char*argv[])|test();return0;)voidtestl(){intarea_limt[]={2,lJ3Jl};inti=0;for(i=0;i<7;i++){printf("%d\n'\get_area__num(area_limt,4,i));))voidtest(){inti=0;get__num_area(&N);get_num_person(&M);get_area_max(N,&area_max);get_love_matrix(N,M,&love);person_num=(int*)malloc(sizeof(int)*M);for(i=0;i<M;i++)(person_num[i]=i;)//print_info(love,N*M);pai_lie(person_num,0,M-I);printf(H\n\n\n");printf("themax_resultis:%d\n"Jmax_result);printf("\n");return;voidget_num_area(int*N){printf("Pleaseinputarea(N):");scanf("%d'\N);return;)voidget_num_person(int*M){printf("Pleaseinputperson(M):");scanf("%d",M);return;)voidget_area_max(intN,int**area_max){inti;printf("Pleaseinputarea_max(a[l..N]):");*area_max=(int*)malloc(sizeof(int)*N);i=0;while(i<N){scanf("%d",*area_max+i);i++；)return;voidget_love_matrix(intN,intM,int**love){inti;printf("Pleaseinputpersonlove(matrix):\n");*love=(int*)malloc(sizeof(int)*N*M);i=0;while(i<N*M){scanf("%d",*love+i);)printf("\n\n\n");return;)voidpai_lie(int*shu_lie,intstart,intend){inti;intj=0;intarea_num=0;if(start==end)max_result_temp=0;for(j=0;j<M;j++)area_num=get_area_num(area_max?j);max_result_temp+=love[shu_lie[j]*N+area__num];if(max_result_temp>max_result)(max_result=max_result_temp;))for(i=0;i<=end;i++){printf("%d\t\shu_lie[i]);}printf("\n");printf("themax_result_tempis:%d\n"Jmax_result_temp);printf("\n");// printf("themax_resultis:%d\n”,max_result);// printf("\n");return;)else{for(i=start;i<=end;i++)swap_num(&shu_lie[start],&shu_lie[i]);pai_lie(shu_lie,start+ljend);swap_nu