西安交通大学算法上机实验报告

《计算机算法设计与分析》上机实验报告姓名：班级：学号：日期：2016年12月23日算法实现题3-14最少费用购物问题★问题描述：商店中每种商品都有标价。例如，一朵花的价格是2元，一个花瓶的价格是5元。为了吸引顾客，商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组，并降价销售。例如，3朵花的价格不是6元而是5元。2个花瓶加1朵花的优惠价格是10元。试设计一个算法，计算出某一顾客所购商品应付的最少费用。★算法设计：对于给定欲购商品的价格和数量，以及优惠价格，计算所购商品应付的最少费用。★数据输入：由文件input.txt提供欲购商品数据。文件的第1行中有1个整数B（0≤B≤5），表示所购商品种类数。在接下来的B行中，每行有3个数C,K和P。C表示商品的编码（每种商品有唯一编码），1≤C≤999；K表示购买该种商品总数，1≤K≤5；P是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，一次最多可购买5*5=25件商品。由文件offer.txt提供优惠商品价数据。文件的第1行中有1个整数S（0≤S≤99），表示共有S种优惠商品组合。接下来的S行，每行的第1个数描述优惠商品组合中商品的种类数j。接着是j个数字对（C，K），其中C是商品编码，1≤C≤999；K表示该种商品在此组合中的数量，1≤K≤5。每行最后一个数字P（1≤P≤9999）表示此商品组合的优惠价。★结果输出：将计算出的所购商品应付的最少费用输出到文件output.txt。输入文件示例输出文件示例Input.txtoffer.txtoutput.txt221473217358252718210解：设cost（a，b，c，d，e）表示购买商品组合（a，b，c，d，e）需要的最少费用。A[k]，B[k]，C[k]，D[k]，E[k]表示第k种优惠方案的商品组合。offer（m）是第m种优惠方案的价格。如果cost（a，b，c，d，e）使用了第m种优惠方案，则cost（a，b，c，d，e）=cost（a-A[m]，b-B[m]，c-C[m]，d-D[m]，e-E[m]）+offer（m）即该问题具有最优子结构性质。按此递归式，设计此问题的动态规划算法如下。1.#includeiostream2.#includecstdio3.#includealgorithm4.#includecstring5.#includequeue6.#includeset7.#includemap8.#includetime.h9.usingnamespacestd;10.11.intsale[1000][6]={0};//分别表示每个优惠中每个商品数量12.intsaleprice[1000]={0};//优惠总价13.intsalelength[1000]={0};//优惠总共有几个商品14.intsalenumber[1000][1000]={0};//优惠商品的ID15.intgood[6][4]={0};//1-number2-price3-lastnum16.intnum[1000];//商品ID17.intdp[6][6][6][6][6];18.intn,m;19.20.voidinput()21.{coutinput.txtendl;22.cinn;23.for(inti=1;i=n;i++)24.{25.cingood[i][1]good[i][3]good[i][2];26.num[i]=good[i][1];27.}28.coutoffer.txtendl;29.cinm;30.for(inti=1;i=m;i++)31.{32.cinsalelength[i];33.for(intj=1;j=salelength[i];j++)34.{35.cinsalenumber[i][j];36.cinsale[i][salenumber[i][j]];37.}38.cinsaleprice[i];39.}40.}41.42.voidoutput()43.{44.for(inti=1;i=n;i++)45.coutgoodnum:good[i][1]goodprice:good[i][2]goodlast:good[i][3]endl;46.for(inti=1;i=m;i++)47.{48.//coutsalelength[i]endl;49.coutsalei:;50.for(intj=1;j=salelength[i];j++)51.coutnum:salenumber[i][j]count:sale[i][salenumber[i][j]];52.coutendl;53.coutprice:saleprice[i]endl;54.55.}56.}57.intmain()58.{59.//freopen(in2,r,stdin);60.input();61.//output();62.dp[0][0][0][0][0]=0;63.for(inti=0;i=good[1][3];i++)64.for(intj=0;j=good[2][3];j++)65.for(intk=0;k=good[3][3];k++)66.for(intl=0;l=good[4][3];l++)67.for(intp=0;p=good[5][3];p++)68.{69.intminx=i*good[1][2]+j*good[2][2]+k*good[3][2]70.+l*good[4][2]+p*good[5][2];71.for(intq=1;q=m;q++)72.{73.if(i-sale[q][num[1]]0||i-sale[q][num[2]]0||i-sale[q][num[3]]0||i-sale[q][num[4]]0||i-sale[q][num[5]]0)continue;74.intt=dp[i-sale[q][num[1]]][j-sale[q][num[2]]][k-sale[q][num[3]]][l-sale[q][num[4]]][p-sale[q][num[5]]]+saleprice[q];75.76.if(tminx)minx=t;77.}78.79.dp[i][j][k][l][p]=minx;80.}coutoutput.txtendl;81.coutdp[good[1][3]][good[2][3]][good[3][3]][good[4][3]][good[5][3]]endl;82.return0;83.}输出结果：算法实现题3-15收集样本问题★问题描述：机器人Rob在一个有n*n个方格的方形区域F中收集样本。（i,j）方格中样本的价值为v(i,j)，如图3-8所示。Rob从方形区域F的左上角A点出发，向下或向右行走，直到右下角的B点，在走过的路上，收集方格中的样本。Rob从A点到B点共走2次，试找出Rob的2条行走路径，使其取得的样本总价值最大。★算法设计：给定方形区域F中的样本分布，编程计算Rob的2条行走路径，使其取得的样本总价值最大。★数据输入：由文件input.txt给出输入数据。第1行有1个正整数n，表示方形区域F有n*n个方格。接下来每行有3个整数，前2个表示方格位置，第3个数为该位置样本价值。最后一行是3个0。★结果输出：将计算的最小平均等待时间输出到文件output.txt。解：由于机器人只能往右走或向下走，所以如果每个位置走过后，它左边或上边的点就不需要考虑了。每个机器人到达终点时都经过2*n-1步。可以设h[x1][y1][x2][y2]表示第一个机器人到达(x1,y1)第二个机器人走到(x2,y2)时的最优值。如果现在为第S步，如果某个机器的X坐标被确定，那么它的Y坐标也可以推出来（有X+Y=S–2)。于是我们可以有在第由第S步的最大值去更新S+1步的最大值即可。而在S步时，可以根据所在的两个位置选择一个方向进行推导（共四个，每个机器人往下或往右）。更新时需要注意如果两个机器人走到同一个格子时，它的值只更新一次（每个样本只能收集一次）。代码如下：ackageexercise;importjava.io.BufferedWriter;importjava.io.FileReader;importjava.io.FileWriter;importjava.io.IOException;importjava.util.Scanner;importsupportclass.SampleGet;publicclassCh3_R3_15{publicstaticvoidmain(String[]args)throwsIOException{//TODOAuto-generatedmethodstubSampleGetcurSamplemap=getSample();curSamplemap.getBestSample();BufferedWriteroutput=newBufferedWriter(newFileWriter(output.txt));//将结果通过output.write()输出output.write(+curSamplemap.getResult());output.close();}publicstaticSampleGetgetSample()throwsIOException{Scannerinput=newScanner(newFileReader(input.txt));input.useDelimiter(\n);intsampleamount=Integer.parseInt(input.next().trim());SampleGetsamplemap=newSampleGet(sampleamount);while(true){String[]cur=input.next().split();if(Integer.parseInt(cur[2].trim())!=0){samplemap.setSamplePoint(Integer.parseInt(cur[0]),Integer.parseInt(cur[1]),Integer.parseInt(cur[2].trim()));}else{break;}}input.close();returnsamplemap;}}packagesupportclass;publicclassSampleGet{int[][]samplemap;int[][][][]mostvalue;intrank;publicSampleGet(intrank){//TODOAuto-generatedconstructorstubthis.rank=rank;samplemap=newint[rank*2][rank*2];mostvalue=newint[rank*2][rank*2][rank*2][rank*2];}publicintgetRank(){returnrank;}publicvoidgetBestSample(){for(ints=2;s=2*rank-1;++s){for(intx1=1;x1=s-1;++x1){for(intx2=1;x2=s-1;++x2){inty1=s-x1;inty2=s-x2;intvalue=mostvalue[x1][y1][x2][y2];dynamicUpdate(x1+1,y1,x2+1,y2,value);dynamicUpdate(x1+1,y1,x2,y2+1,value);dynamicUpdate(x1,y1+1,x2+1,y2,value)