钢条切割问题(Java)——Bottom-up DP演算法

小鱼儿 2022-04-11 11:15 206阅读 0赞

### Rod Cutting题目: ###

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

*  注意:

1.  本题采用txt文件读入,屏幕输出;  
    如果需要屏幕读入屏幕输出,可以留言或者自己改代码~
2.  Bottom-up DP演算法:因为Top-down DP演算法有很多重复的计算,因此进一步改进Top-down DP演算法得到Bottom-up DP演算法。在第一次计算中把分割结果以及最大利润的结果记录下来，下次需要用到的时候直接调用,节省时间。——所需时间T=O( n^2)

import java.beans.IntrospectionException;
    import java.io.BufferedReader;
    import java.io.FileNotFoundException;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.Scanner;
    
    public class BottomupDP {
    	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的长度
    		 		System.out.println("Maximum revenue: "+extendedBottomUpCutRod(Price,n));
    		 		printCutRodSol(Price,n);
    		 		
    		 	} 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.println("方法:Bottom-up DP算法 ; 执行时间： "+(endTime-startTime)+" ms");	
    	}
    	static int[] s=new int[100];
    	static int extendedBottomUpCutRod(int p[] ,int n) {
    		 int[] r=new int[n+1];
    		 r[0]=0;
    		 s[0]=0;
    //	    if(r[n] != -1)
    //	        return r[n];
    	    for(int i = 1; i <= n; i++) {// 双层循环建立r和s数组存入切割点以及最大利润
    	        int q =Integer.MIN_VALUE;
    	        for(int j = 1; j <= i; j++) {
    		        	if(q<p[j] + r[i - j])//q为:每个长度的Rod最大的max值
    		        	{
    		        		q=p[j] + r[i - j];
    		        		s[i] = j;//s记录下获得最大价值的切割点
    		        	}
    	            }
    	        //System.out.print(s[i]+" ");
    	        r[i] = q;//将最大值存入r[i]
    	        }
    	    return r[n];
    	}
    	 
    	static void printCutRodSol(int p[],int n) {//输出Cuts的位置
    		System.out.print("Cuts:");
    		while(n > 0) {
    			System.out.print(s[n]+" ");//找到n对应的切割点
    			n=n-s[n];
    		}
    		System.out.println();
    	}
    
    }

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDg2NTAx_size_16_color_FFFFFF_t_70]: /images/20220411/7caabdce7323462eb49f5436055a935d.png
[2018120522082179.png]: /images/20220411/a79ab25c209a4c62b51214d2b0837174.png