钢条切割问题(Java)——暴力法(Brute force)

╰+哭是因爲堅強的太久メ 2022-04-11 11:13 247阅读 0赞

### Rod Cutting题目: ###

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

*  注意:

1.  本题采用txt文件读入,屏幕输出;  
    如果需要屏幕读入屏幕输出,可以留言或者自己改代码~
2.  说明:暴力法(Brute force): 列出每种切割方案，比较哪种切割方案利润最大,——所需时间T=O(2^n )

import java.io.BufferedReader;
    import java.io.FileNotFoundException;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.Scanner;
    
    public class Bruteforce {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		long startTime = System.currentTimeMillis();
    		try {
    		FileReader in = new FileReader("p2.txt");
    		BufferedReader inin=new BufferedReader(in);//读入文件
    		 	try {
    		 		String s="";
    		 		int i=0;		 		
    				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: "+Cut_Rod(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.print("方法:暴力法(Brute force); 执行时间： "+(endTime-startTime)+" ms");//求得程式执行时间
    	}
    	static int Cut_Rod(int price[],int n)//Bruteforce暴力法: 求解最大利润
    	{
    		if(n==0)
    			{  return 0;}//无法切割: return 0
    		else{
    			int  q=Integer.MIN_VALUE;//q无穷小
    			for(int i=1;i<=n;i++)
    			{
    				q=Math.max(q, price[i-1] + Cut_Rod(price, n - i));//取q和已分割求得的价值中取max
    			}
    			//System.out.println(q+" ");
    			return q;
    		}		
    	}
    }

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDg2NTAx_size_16_color_FFFFFF_t_70]: /images/20220411/bbc4a09eb8a5414a9ad4a42424be0dba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDg2NTAx_size_16_color_FFFFFF_t_70 1]: /images/20220411/a250c2c7f3c64982bc527d8f89f8426e.png