钢条切割问题(Java)——Top-down DP演算法

谁借莪１个温暖的怀抱￠ 2022-04-11 11:15 209阅读 0赞

### Rod Cutting题目: ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDg2NTAx_size_16_color_FFFFFF_t_70]

*  注意:

1.  本题采用txt文件读入,屏幕输出;  
    如果需要屏幕读入屏幕输出,可以留言或者自己改代码~
2.  Top-down DP演算法: 从钢条的左边切割下一段长度为i的短钢条，然后右边为长度即为n-i的短钢条，进一步对右边继续递归求解，直到右边的长度为0，则返回零。  
    ——所需时间T=O( n^2)

import java.io.BufferedReader;
    import java.io.FileNotFoundException;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.Scanner;
    
    public class TopdownDP {
    		public static void main(String[] args) {
    			// TODO Auto-generated method stub
    			long startTime = System.currentTimeMillis();
    			try {
    			FileReader in = new FileReader("p1.txt");
    			BufferedReader inin=new BufferedReader(in);//读入文件
    			 	try {
    			 		String s="";
    			 		int i=1;		 		
    					int[] Length=new int[100];//Rod的长度
    					int[] Price=new int[100];//Rod的价值
    			 		while((s=inin.readLine())!=null)
    			 		{  
    				 		//System.out.println(s);
    				 	    //将每一行分为两个整数
    				 		String []data=s.split(" ");
    				 		//System.out.println("长度"+data.length);
    				 		int [] datas=new int[data.length];//存入每一行String类型的数组data[0]  data[1]  
    				 		//将String类型数组转成int类型
    				 		for(int j=0;j<data.length;j++)
    				 		{   datas[j]=Integer.parseInt(data[j]); } //将String类型转换成int类型
    		//		 		for(int i=0;i<datas.length;i++)
    		//		 		{    System.out.println(i+" "+datas[i]+" ");   } 	
    				 		Length[i]=datas[0]; //获取Rod的长度
    				 		Price[i]=datas[1];  //获取Rod的价值
    				 		//System.out.println(data);
    				 			i++;
    			 		}
    //			 		for(int k=0;k<i;k++)
    //			 		{    System.out.println(k+" "+Length[k]+" ");   } //Rod的长度Length
    //			 		for(int k=0;k<i;k++)
    //			 		{    System.out.println(k+" "+Price[k]+" ");   } //Rod的价格Price
    			 		Scanner scanner=new Scanner(System.in);
    			 		System.out.print("请输入Rod的长度: ");
    			 		int n=scanner.nextInt();//Rod的长度
    			 		int[] r=new int[100];
    			 		System.out.println("Maximum revenue: "+Memoized_Cut_Rod(Price,n)); //Top-down dynamic programming(DP)求解
    
    			 	} catch (IOException e) {
    					// TODO Auto-generated catch block
    					e.printStackTrace();
    				}
    			} catch (FileNotFoundException e) {
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    			long endTime = System.currentTimeMillis();
    		    System.out.print("方法: Top-down DP算法;  执行时间： "+(endTime-startTime)+" ms");//求得程式执行时间
    		}
    		
    		static int Memoized_Cut_Rod(int price[],int n)
    		{
    			int[] r=new int[n+1];
    			for(int i=0;i<n+1;i++)
    			{
    				r[i]=Integer.MIN_VALUE;//初始化数组r, r[i]表示:每个对应长度的最大利润
    			}
    			return MemoizedCutRodAux(price,n,r);
    		}
    		
    		static int MemoizedCutRodAux(int price[], int n, int r[])
    		{
    			int q ;
    			if (r[n] >= 0)
    				{  return r[n];}//首先检查所需的值是否存在
    			if (n == 0)
    				{ q = 0; }
    			else{
    				q=Integer.MIN_VALUE;
    			 for (int i = 1; i <= n; ++i){	
    				 q=Math.max(q, price[i] + MemoizedCutRodAux(price, n - i, r));//取q和已分割求得的价值中取max,q即为最大利润
    				  }
    			}
    			r[n] = q; //使每个对应长度的最大利润r[i]为q(最大利润)
    			return q;//返回此时的最大值,用于循环求解最大利润
    		}
    }

运行成功,截图如下:  
![在这里插入图片描述][20181205220750649.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDg2NTAx_size_16_color_FFFFFF_t_70]: /images/20220411/493f5c24e6904fa88f7bf091765f1823.png
[20181205220750649.png]: /images/20220411/3b2f53ff22e94a4a99170265a67bcfcc.png