java - メモ化:Rememo

Question

配列memo[][]は、にある布を返していmemo[X][Y]ます。このクラスをテストしたところ、 に収まる最初の布のみが保存されるように見えますがmemo[X][Y]、 に収まる最も価値のある布を返したいと思いますmemo[X][Y]。これどうやってするの？

class ClothCutter {
    static ArrayList <Pattern> patterns; //array of patterns to try
    static Cloth maxCloth; //the maximum cloth 
    static Cloth memo[][]; // memo for maximum cloth (X,Y), memo[X][Y]
    int width;
    int height;

    //Constructor
    public ClothCutter(int w, int h,ArrayList<Pattern> p) {
        width = w;
        height = h;
        patterns = p;
        maxCloth = new Cloth(w,h);
        memo = new Cloth [w+1][h+1];
        for (int i = 0; i<patterns.size();i++)  {
            Pattern z = patterns.get(i);
            System.out.println(z.name);
            Cloth m = new Cloth(z.width,z.height);
            m.add(z);
            memo[z.width][z.height]=m;
            System.out.println(memo[z.width][z.height].value);
        }
    }

    public Cloth optimize() {
        return optimize(maxCloth);
    }

    public Cloth optimize(Cloth c){
        Cloth temp1 = new Cloth(); 
        Cloth temp2 = new Cloth();
        Cloth max = new Cloth(c.width,c.height);//temporary max

        if (memo[c.width][c.height]!=null) // return memo if there is one
            return memo[c.width][c.height];
        if (c.width==0||c.height==0) //if (X||Y ==0)
            memo[c.width][c.height]=max;
            return max;
        }

        for (int i=0;i<patterns.size();i++) { //for each pattern
            Pattern p = patterns.get(i);
            if (p.width<=c.width && p.height<=c.height) {
                if (p.width<c.width) {
                    //if the pattern's width is less than the cloth's width
                    Cloth a = new Cloth(c.width-p.width,c.height);//cut vertically
                    a.pattern = p;
                    Cloth b = new Cloth(p.width,c.height);//remainder after vertical cut
                    b.pattern = p;

                    temp2=optimize(b);//recurse 
                    temp1=optimize(a);//recurse
                }
                if (c.width==p.width) {
                    //if the cloth's width is equal to a patterns with start cutting horizontally 
                    Cloth a = new Cloth(c.width,c.height-p.height);//horizontal cut
                    a.pattern=p;
                    Cloth b = new Cloth(c.width,p.height);//remainder after horizontal cut
                    b.pattern = p;
                    temp2=optimize(b);//recurse
                    temp1=optimize(a);//recurse
                }
                if (temp1.value+temp2.value>max.value) {
                    //if the value of the optimal cloths is greater than the value of max
                    max.add(temp1,temp2);//add the two cloths to max
                    max.pattern = p;
                    if (max.width == maxCloth.width && max.height == maxCloth.height && maxCloth.value < max.value)
                        // if the max dimentions is equal to maxCloth dimetions and the value of the maxCloth is less than max
                        maxCloth=max;//set maxCloth to max
                }
            }
        }

        if (memo[max.width][max.height]==null) //if memo is equal to null
            memo[max.width][max.height]=max;// create memo  
    return max;
    }

Answer 1

あなたのコードは私が問題をすぐに理解するのを少し混乱させましたが、私は友人のためにこの疑似コードを書いたばかりで、私のものを実行すると常に適切な最適値が得られました。比較できるかも！

optimize() {

    Rectangle memo[width][height]
    optimize(0,0,totalwidth, totalheight, memo)
}

optimize(x, y, width, height, memo) {

    if memo[width][height] != null
        return memo[width][height]

    rect = new Rectangle(width, height, value = 0)
    for each pattern {

        //find vertical cut solution
        leftVerticalRect = optimize (x, y + pattern.height, pattern.width, height-pattern.height,memo)
        rightVerticalRect = optimize(x  + pattern.width, y, width-pattern.width, height)
        verticalcut = new Cut(x + pattern.width, y, x + pattern.width, y + height)

        //find horizontal cut solution
        topHorizontalRect = optimize ( --parameters-- )
        bottomHortizonalRect = optimize( --parameters--)
        horizontalcut = new Cut( --parameters--)

        //see which solution is more optimal
        if (leftVerticalRect.val + rightVerticalRect.val > topHorizontalRect.val + bottomHorizontalRect.val)
            subprobsolution = vertical cut solution
        else
            subprobsolution = horizontal cut solution

        //see if the solution found is greater than previous solutions to this subproblem
        if (subprobsolution.value + pattern.value > rect.value) {
            rect.subrect1 = subprobsolutionrect1
            rect.subrect2 = subprobsolutionrect2
            rect.pattern = pattern
            rect.cut = subprobsolutioncut
            rect.value = rect.subrect1.value + rect.subrect2.value + rect.pattern.value
        }
    }

    memo[width][height] = rect
    return rect
}