搜索
算法导论课程设计——最少费用购物问题、最短加法链问题学号：1206010113姓名：齐海班级：计算机一班教师：施小华最少费用购物问题一、问题分析由于所购商品不超过5种，而每种采购的数量又不超过5，那么用一个五元组来表示第I种商品买AI的最小费用。F（A1，A2，A3，A4，A5）（1）考虑这个状态的由来，当然，我们不用优惠商品也可以买，显然这样不是最优。假设商品组合有k种，于是如果我们能够使用第I条商品组合的话，状态就便为了：F（A1-SI1，A2-SI2，A3-SI3，A4-SI4，A5-SI5）（2）这样的话，状态1的费用为状态2的费用加上SI的费用，而状态2的费用必须最低（很显然，用反证法即可），同时，我们也不管状态2是如何来的（因为每一个优惠商品组合的使用是没有限制的），所以本题既满足无后效性，又符合最优化原理，同时还有大量重叠子问题产生，动态规划解决此题是最好不过了。通过对问题的分析，我们知道了状态的表示和转移的基本方法，我们很容易得到一个状态转移方程：F[a,b,c,d,e]=Min{F[a-SI1,b-SI2,c-SI3,d-SI4,e-SI5]+SaleCost[S]}其中I∈(0,k]初始条件为：F[a,b,c,d,e]=Cost[1]*a+Cost[2]*b+Cost[3]*c+Cost[4]*d+Cost[5]*e即不用优惠的购买费用。二、代码/***@author齐海*计算机一班1206010113*最少费用购物问题*动态规划算法*/importjava.io.*;importjava.util.ArrayList;classGoods{int[]code={0,0,0,0,0};//商品的编码int[]kind={0,0,0,0,0,0};//购买该种商品的总数，kind[5]表示总价int[]cost={0,0,0,0,0,0};//每件商品的价格intB=0;//所购商品种类数intuse=0;//记录使用过优惠组合的总价publicGoods(){//初始化商品类，//要求input.txt文件中按照编码升序排列BufferedReaderbr=null;try{br=newBufferedReader(newFileReader(D:\\input.txt));Stringline=null;line=br.readLine();B=Integer.parseInt(line);inti=0;Stringregex=+;while((line=br.readLine())!=null&&iB){String[]temp=line.split(regex);code[i]=Integer.parseInt(temp[0]);kind[i]=Integer.parseInt(temp[1]);cost[i]=Integer.parseInt(temp[2]);i++;}}catch(Exceptione){e.printStackTrace();}finally{try{if(br!=null)br.close();elsethrownewRuntimeException(文件关闭失败！);}catch(IOExceptione){e.printStackTrace();}}kind[5]=getPrice();}publicintgetPrice(){//计算商品总价（不使用优惠）intp=0;for(inti=0;i5;i++){p=p+kind[i]*cost[i];}returnp;}publicbooleanhasCombos(ArrayListint[]combos){//当前商品是否存在优惠组合for(int[]combo:combos){if(isCombo(combo))returntrue;}returnfalse;}publicbooleanisCombo(int[]combo){//当前商品是否存在优惠组合booleanflag=true;for(intj=0;j5;j++){if(kind[j]combo[j])flag=false;}returnflag;}}publicclassBuyDemo{publicstaticvoidmain(String[]args){//初始化优惠组合BufferedReaderbr=null;intS=0;ArrayListint[]as=newArrayListint[]();try{br=newBufferedReader(newFileReader(D:\\offer.txt));Stringline=null;line=br.readLine();S=Integer.parseInt(line);inti=0;Stringregex=+;while((line=br.readLine())!=null&&iS){String[]temp=line.split(regex);//combo[0]到combo[4]商品在组合中的数量//combo[5]表示优惠组合价格int[]combo=newint[]{0,0,0,0,0,0};intk;for(k=2;ktemp.length;k=k+2){combo[k/2-1]=Integer.parseInt(temp[k]);}combo[5]=Integer.parseInt(temp[temp.length-1]);as.add(combo);i++;}}catch(Exceptione){e.printStackTrace();}finally{try{if(br!=null)br.close();elsethrownewRuntimeException(文件关闭失败！);}catch(IOExceptione){e.printStackTrace();}}Goodsgoods=newGoods();intmin;intindex=0;intprice=0;//当前商品种类状态存在优惠组合时，选择最优惠的组合进入下一状态//不存在优惠组合时循环结束while(goods.hasCombos(as)){min=goods.kind[5];for(inti=0;ias.size();i++){if(goods.isCombo(as.get(i))){int[]temp=newint[6];temp[5]=0;for(intj=0;j5;j++){temp[j]=goods.kind[j]-as.get(i)[j];temp[5]=goods.cost[j]*temp[j]+temp[5];}temp[5]=temp[5]+as.get(i)[5];if(temp[5]min){min=temp[5];index=i;}}}goods.use=goods.use+as.get(index)[5];System.out.println(usecombo+index);System.out.println(goods.use=+goods.use);for(intk=0;k5;k++){goods.kind[k]=goods.kind[k]-as.get(index)[k];System.out.print(goods.kind[k]+);}price=goods.getPrice();goods.kind[5]=price+goods.use;System.out.println(goods.kind[5]);//最少费用存放在king[5]中}//将最少费用写入output.txtBufferedWriterbw=null;try{bw=newBufferedWriter(newFileWriter(D:\\output.txt));bw.write(goods.kind[5]+);bw.flush();}catch(IOExceptione){e.printStackTrace();}finally{try{if(bw!=null)bw.close();elsethrownewRuntimeException(文件关闭失败！);}catch(IOExceptione){e.printStackTrace();}}}}三、测试改变input.txt，offer.txt则输出outout.txt最短加法链问题一、问题分析本题可以通过回溯法来搜索加法链。显然加法链的前两个值为1和2（n=2），通过1和2来生成后续加法链并搜索目标target。在理想情况下，最短加法链长度为log2𝑡𝑎𝑟𝑔𝑒𝑡，即以指数速率生成加法链。在一般情况下，设当前加法链最后一位chain[k]，则chain[k+1]可以由一下方式生成：1.若chain[k]*2=target，chain[k+1]=chain[k]*2，并检测是否到达target2.若chain[k]+chain[k-1]=target，检测0到k-2中是否有元素与chain[k]相加得target3.若chain[k-1]+chain[k]target，则回溯。通过上述加法链的生成和回溯搜索，即得到最短加法链。二、代码/***@author齐海*计算机一班1206010113*最短加法链问题*回溯法*/importjava.io.BufferedReader;importjava.io.BufferedWriter;importjava.io.FileReader;importjava.io.FileWriter;importjava.io.IOException;publicclassMinChain{publicstaticvoidmain(String[]args){//初始化加法链及对应标志位int[]chain=newint[1000];chain[0]=1;chain[1]=2;int[]flag=newint[1000];flag[0]=0;flag[1]=0;intk=1;inttarget=1;//从input.txt中读取targetBufferedReaderbr=null;try{br=newBufferedReader(newFileReader(E:\\input.txt));Stringline=null;line=br.readLine();target=Integer.parseInt(line);System.out.println(target=+target);}catch(Exceptione){e.printStackTrace();}finally{try{if(br!=null)br.close();elsethrownewRuntimeException(文件关闭失败！);}catch(IOExceptione){e.printStackTrace();}}//回溯法搜索加法链while(true){if(chain[k]*2=target){chain[k+1]=chain[k]*2;flag[k+1]=0;k++;if(chain[k]==target)break;continue;}if(chain[k]+chain[k-1]=target){chain[k+1]=chain[k-1]+chain[k];flag[k]=1;flag[k+1]=0;k++;if(chain[k]==target)break;continue;}if(chain[k-1]+chain[k]target){flag[k]=1;for(intt=0;tk-1;t++){if((chain[t]+chain[k])==target){chain[k+1]=target;k=k+1;break;}}if(chain[k]==target)break;while(flag[k]!=0)k--;flag[k]=1;chain[k+1]=chain[