注意:以下是三合一的代碼,如果隻想要:
暴力法(Brute force):
https://blog.csdn.net/qq_37486501/article/details/84844197
Top-down DP演算法:
https://blog.csdn.net/qq_37486501/article/details/84844222
Bottom-up DP演算法:
https://blog.csdn.net/qq_37486501/article/details/84844253
Rod Cutting題目:
-
注意:
本題采用txt檔案讀入,螢幕輸出;
如果需要螢幕讀入螢幕輸出,可以留言或者自己改代碼~
暴力法(Brute force), Top-down DP演算法,Bottom-up DP演算法——(三合一代碼)如下:
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;
class Rod{//建立Rod類,裡面含有
public int[][] extendedBottomUpCutRod(int[] prices, int n) {
int[] revs = new int[n + 1];
int[] size = new int[n + 1];
revs[0] = 0;
int max = Integer.MIN_VALUE;
for (int j = 1; j <= n; j++) {
max = Integer.MIN_VALUE;
for (int i = 0; i < j; i++) {
if (max < prices[i] + revs[j - i - 1]) {
max = prices[i] + revs[j - i - 1];
size[j] = i + 1;
//System.out.print(size[j]+" ");
}
}
revs[j] = max;
}
//For simplicity, return a 2d array where rs[0] is the revs array, rs[1] is the size array.
//This may not be the optimized solution but I think it's cumbersome to create a tuple class in Java so I choose to use a 2D array.
int[][] rs = new int[2][n + 1];
for (int i = 0; i < n + 1; i++) {
rs[0][i] = revs[i];
rs[1][i] = size[i];
//System.out.print(size[i]+" ");
}
return rs;
}
//Naive version: recursive top-down implementation
//Time: O(2^n)
public int cutRod(int[] prices, int n) {
if (n == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; ++i) {
max = Math.max(max, prices[i] + cutRod(prices, n - i - 1));
}
return max;
}
//Dynamic-programming: top-down approach with memoization
//Time: O(n^2)
public int memoizedCutRod(int[] prices, int n) {
int[] revs = new int[n + 1];//revs[i] corresponds to the maximum revenues of length i. We define revs[0] = 0.
for (int i = 0; i < revs.length; i++) {
revs[i] = -1;//we use -1 here to indicate a state that the revs is not cached yet instead of negative infinity in the book because revenue is always nonnegative.
}
return memoizedCutRodAux(prices, n, revs);
}
private int memoizedCutRodAux(int[] prices, int n, int[] revs) {
if (revs[n] >= 0) {
return revs[n];
}
int max = Integer.MIN_VALUE;
if (n == 0) {
max = 0;
} else {
for (int i = 0; i < n; i++) {
max = Math.max(max, prices[i] + memoizedCutRodAux(prices, n - i - 1, revs));
}
}
revs[n] = max;
return max;
}
//Dynamic-programming: bottom-up approach
//Time: O(n^2)
public int bottomUpCutRod(int[] prices, int n) {
int[] revs = new int[n + 1];
revs[0] = 0;//the revenue of a rod of length 0 is 0.
int max = Integer.MIN_VALUE;
for (int j = 1; j <= n; j++) {//revs[j] indicates maximum revenue of a rod of length j.
max = Integer.MIN_VALUE;
for (int i = 0; i < j; i++) {
max = Math.max(max, prices[i] + revs[j - i - 1]);
}
revs[j] = max;
}
return revs[n];
}
public void printCutRodSolution(int[] prices, int n) {
int[][] revsAndSize = extendedBottomUpCutRod(prices, n);
int maxRevenue = revsAndSize[0][n];
int[] size = revsAndSize[1];
System.out.print("Cuts:");
while (n > 0) {
System.out.print(size[n]+" ");
n -= size[n];
}
System.out.println();
System.out.println("max revenue: "+maxRevenue);
}
}
public class RodCutting {
public static void main(String[] args) {
try {
FileReader in = new FileReader("p1.txt");
BufferedReader inin=new BufferedReader(in);//讀入檔案
try {
String s="";
int i=0;
int[] Length=new int[1000];
int[] prices=new int[1000];
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類型數組轉成int類型
for(int j=0;j<data.length;j++)
{
datas[j]=Integer.parseInt(data[j]);
//System.out.println(j+" "+data[j]);
}
// for(int i=0;i<datas.length;i++)
// { System.out.println(i+" "+datas[i]+" "); }
Length[i]=datas[0];
prices[i]=datas[1];
//System.out.println(data);
i++;
}
// for(int k=0;k<i;k++)
// { System.out.println(k+" "+Length[k]+" "); } //長度Length
// for(int k=0;k<i;k++)
// { System.out.println(k+" "+Price[k]+" "); } //價格Price
Scanner scanner=new Scanner(System.in);
System.out.println("請輸入Rod的長度: ");
int n=scanner.nextInt();
//System.out.println(Cut_Rod(Price,n));
Rod rc = new Rod();
int max0 =0;
int max1 =0;
int max2 =0 ;
for (int i1 = 0; i1 <= n; i1++) {
max0 = rc.cutRod(prices, i1);
max1 = rc.memoizedCutRod(prices, i1);
max2 = rc.bottomUpCutRod(prices, i1);
// System.out.printf("recursive max: %d%n", max0);
// System.out.printf("memoized max: %d%n", max1);
// System.out.printf("bottomUp (dp) max: %d%n", max2);
//rc.printCutRodSolution(prices, i1);
//System.out.println("----------------");
}
System.out.println("Rod Length:"+n);
System.out.printf("recursive max: %d%n", max0);
System.out.printf("memoized max: %d%n", max1);
System.out.printf("bottomUp (dp) max: %d%n", max2);
rc.printCutRodSolution(prices, n);
// rc.printCutRodSolution(prices, max0);
// System.out.println("----------------");
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
運作成功, 截圖如下:
