注意:以下是三合一的代码,如果只想要:
暴力法(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]+" "); } //价格PriceScanner 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 blocke.printStackTrace();}} catch (FileNotFoundException e) {// TODO Auto-generated catch blocke.printStackTrace();}}}运行成功, 截图如下:
