【动态规划1】钢条切割算法Java代码

import java.util.Scanner;

public class RodCutttingProblem {

    static int [] price = {1,5,8,9,10,17,17,20,24,30};
     static BestCut [] bestCuts;
    public static void main(String []args){
        System.out.println("please input the rod length:");
        Scanner sc = new Scanner(System.in);
        int rodLength = sc.nextInt();
        bestCuts= new BestCut[rodLength];

        for (int i=0;i<rodLength;i++){
            bestCuts[i] = new BestCut();
        }
        bestCuts[0].price = price[0];
        bestCuts[0].cutMethod = ":1:";

        BestCut test = cutTheRod(rodLength);

        System.out.println("best price is: "+bestCuts[rodLength-1].price);
        System.out.println("best cut method is: "+bestCuts[rodLength-1].cutMethod);
    }

    public static BestCut cutTheRod(int rodLength){
        BestCut bestCutFirstPart = new BestCut();//切割的前段最好值
        BestCut bestCutSecondPart = new BestCut();//切割后段最好值
        System.out.println("orgrodlength"+rodLength);


        BestCut bestCutResult = new BestCut();
        if(rodLength <=1){
            bestCutResult.price=bestCuts[0].price;
            bestCutResult.cutMethod  =":1:";
            return bestCutResult;
        }
        System.out.println("the price length is: "+price.length);
        System.out.println("the rod leght is: "+rodLength);
        for (int i=1;i<=rodLength;i++){
            if (i<=price.length){
                bestCutFirstPart.price = price[i-1];
                bestCutFirstPart.cutMethod = ":"+i+":";
            }
            else {
                System.out.println("the cut place is: "+i);
                bestCutFirstPart.price = bestCuts[i-2].price+bestCuts[0].price;
                bestCutFirstPart.cutMethod = ":"+i+":"+":"+1+":";
            }

            if (i==rodLength){
                bestCutResult.price = bestCutFirstPart.price;
                bestCutResult.cutMethod = bestCutFirstPart.cutMethod;
                if (bestCuts[rodLength-1].price<bestCutResult.price){
                    bestCuts[rodLength-1].price = bestCutResult.price;
                    bestCuts[rodLength-1].cutMethod = bestCutResult.cutMethod;
                }
                continue;
            }

            //计算后面的钢段的值
            if (bestCuts[rodLength-i-1].price==0){
                //计算第一段最好的值
                bestCutSecondPart =cutTheRod(rodLength-i);
            }
            else {
                bestCutSecondPart.price= bestCuts[rodLength-i-1].price;
                bestCutSecondPart.cutMethod = bestCuts[rodLength-i-1].cutMethod;
            }

            bestCutResult.price = bestCutFirstPart.price+ bestCutSecondPart.price;
            bestCutResult.cutMethod = bestCutFirstPart.cutMethod+bestCutSecondPart.cutMethod;
            if (bestCuts[rodLength-1].price<bestCutResult.price){
                bestCuts[rodLength-1].price = bestCutResult.price;
                bestCuts[rodLength-1].cutMethod = bestCutResult.cutMethod;
            }
        }

        return bestCutResult;
    }

}

class BestCut{
    int price;
    String cutMethod;
}