【精品】算法分析解题报告。.doc

《【精品】算法分析解题报告。.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法分析结题报告姓名：秦志新班级：计算机092学号：09109206UserID:09109206Password:09109206题目一、动态规划101CommunicationSystemTimeLimit:1000MSMemoryLimit:10000KTotalSubmissions:16957Accepted:5962DescriptionWehavereceivedanorderfromPizoorCommunicationsInc.foraspecialcommunicationsy

2、stem.Thesystemconsistsofseveraldevices・Foreachdevice,wearefreetochoosefromseveralmanufacturers.Samedevicesfromtwomanufacturersdifferintheirmaximumbandwidthsandprices.Byoverallbandwidth(B)wemeantheminimumofthebandwidthsofthechosendevicesinthecommunicat

3、ionsystemandthetotalprice(P)isthesumofthepricesofallchosendevices・OurgoalistochooseamanufacturerforeachdevicetomaximizeB/P.InputThefirstlineoftheinputfilecontainsasingleintegert(it<10),thenumberoftestcases,followedbytheinputdataforeachtestcase.Eachtes

4、tcasestartswithalinecontainingasingleintegern(1

5、sinthesameline,eachindicatingthebandwidthandthepriceofthedevicerespectively,correspondingtoamanufacturer.OutputYourprogramshouldproduceasinglelineforeachtestcasecontainingasinglenumberwhichisthemaximumpossibleB/Pforthetestcase・Roundthenumbersintheoutp

6、utto3digitsafterdecimalpoint.SampleInput13310025150358025212080155402100100120110SampleOutput0.649SourceTehran2002,FirstIranNationwideInternetProgrammingContest解决办法：如果采用爆搜的话,时间肯定是不允许的。而从题意可知,如果加宽大而且价格便宜，那么这就更加有可能被选择到的;但如果我们开始爆搜价格之和的话，那将十分困难。我们可以先爆搜加宽b

7、andwide撚后我们再用i从banclwide的low到high枚举，在每种产品选择中搜索加宽bandwide>=i与price较小者.再用贪心选择与更新的result(B/P的最大值)。源代码:#includet,stdio.ht,intinain()freopcn(HLtxt,stdin);intt,n,m[100],b[100][l()0],p[100][1()0];〃输入的值inti,j,k;〃辅助变量inthigh,low,temp,sum;doubleresult;scanf(tl

8、%d,&t);while(t・・){scanfC^d1；&n);〃设置初值，以便赋值.high=0;low=32767;〃获得一个最小和最大带宽:最小带宽z是各个设备最大带宽的最小值,〃最大带宽high是各个设备最大带宽的最大值.〃枚举band的最小值与最大值.for(i=0;ihigh){high=b[