Rod Cutting题目:
- 注意:
- 本题采用txt文件读入,屏幕输出;
如果需要屏幕读入屏幕输出,可以留言或者自己改代码~ - 说明:暴力法(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 stublong 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的价格PriceScanner 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 blocke.printStackTrace();}} catch (FileNotFoundException e) {// TODO Auto-generated catch blocke.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 0else{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;} }
}运行成功,截图如下:
