钢条切割--动态规划--算法导论

梦里梦外; 2022-06-17 08:39 172阅读 0赞

在网上看到很多钢条切割的代码，很多都是C++，用到结构体，内联函数，const变量，复杂......直接写了一段java简单的代码

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[] p = {0,1,5,8,9,10,17,17,20,24,30};//对应长度是0,1,2,3,4,5,6,7,8,9,10的整段价值
            int[] r = new int[n+1];//最大价值
            int[] s = new int[n+1];//分段情况
            Main main = new Main();
            main.cutRodExtend(n,p,r,s);
            sc.close();
        }
        private  void  cutRodExtend(int n,int[] p,int[] r,int[] s){
            r[0] = 0;
            int q;
            int tmp;
            for(int i = 1;i<=n ;i++){
                q = -1;
                for(int j = 1;j<=i;j++){
                    tmp = p[j] + r[i-j];
                    if(tmp >q){
                        q = tmp ;
                        s[i] = j;
                        //r[i] = tmp;//写在这里也行
                    }
                }
                r[i] = q;//写在这里也行,此处是先对1,2,3长度的分段求出最大值，保存在r[1],r[2],r[3]中，后面的n=4时就是p[1]+r[3],p[2]+r[2],p[3]+r[1]....原来的1,2,3长度的最大值可以直接拿来用
            }
            System.out.println("最大价值是:"+r[n]);
            System.out.print("分段是:");
            while(n > 0){
                System.out.print(s[n]+" ");
                n  = n - s[n];
            }
        }//cutRodExtend
    }

"C:\Program Files\Java\jdk1.6.0_43\bin\java" -agentlib:jdwp=transport=dt_socket,address=127.0.0.1:50440,suspend=y,server=n -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.6.0_43\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.6.0_43\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.6.0_43\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.6.0_43\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.6.0_43\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.6.0_43\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.6.0_43\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.6.0_43\jre\lib\jce.jar;C:\Program Files\Java\jdk1.6.0_43\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.6.0_43\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.6.0_43\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.6.0_43\jre\lib\resources.jar;C:\Program Files\Java\jdk1.6.0_43\jre\lib\rt.jar;G:\IdeaProjects\钢条切割--动态规划\out\production\钢条切割--动态规划;D:\Program Files (x86)\JetBrains\IntelliJ IDEA 2016.2\lib\idea_rt.jar" Main
    Connected to the target VM, address: '127.0.0.1:50440', transport: 'socket'
    7
    最大价值是:18
    分段是:1 6 Disconnected from the target VM, address: '127.0.0.1:50440', transport: 'socket'
    
    Process finished with exit code 0