Memoization: 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

Ваш код был немного запутанным для меня, чтобы выяснить проблему быстро, но я просто написал эту psuedocode для моего друга, и я всегда получал правильное оптимальное значение, когда я управлял моим. Возможно, вы можете сравнить!

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 
}