Rod Cutting題目:
- 注意:
-
本題采用txt檔案讀入,螢幕輸出;
如果需要螢幕讀入螢幕輸出,可以留言或者自己改代碼~
- 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();
}
}
運作成功,截圖如下:
