钢条切割问题——(暴力法(Brute force), Top-down DP演算法,Bottom-up DP演算法)对比

ゞ浴缸里的玫瑰 2022-04-11 11:16 168阅读 0赞

注意:以下是三合一的代码,如果只想要:  
暴力法(Brute force):  
[https://blog.csdn.net/qq\_37486501/article/details/84844197][https_blog.csdn.net_qq_37486501_article_details_84844197]  
Top-down DP演算法:  
[https://blog.csdn.net/qq\_37486501/article/details/84844222][https_blog.csdn.net_qq_37486501_article_details_84844222]  
Bottom-up DP演算法:  
[https://blog.csdn.net/qq\_37486501/article/details/84844253][https_blog.csdn.net_qq_37486501_article_details_84844253]

### Rod Cutting题目: ###

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

*  注意:  
    本题采用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();
        		}
        }
        
    }

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

[https_blog.csdn.net_qq_37486501_article_details_84844197]: https://blog.csdn.net/qq_37486501/article/details/84844197
[https_blog.csdn.net_qq_37486501_article_details_84844222]: https://blog.csdn.net/qq_37486501/article/details/84844222
[https_blog.csdn.net_qq_37486501_article_details_84844253]: https://blog.csdn.net/qq_37486501/article/details/84844253
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDg2NTAx_size_16_color_FFFFFF_t_70]: /images/20220411/708b4e263ac54cf297748a6545f4b257.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDg2NTAx_size_16_color_FFFFFF_t_70 1]: /images/20220411/d73ff58fd1184c5dbe2b2191cbbe4014.png