Динамические прог. Algo Прямоугольник Упаковка

Question

У меня есть задача о назначениях

Вам дается набор из п 2-мерных прямоугольников. Вам необходимо найти максимальную возможную упаковку подмножества прямоугольников размером . При упаковывании мы имеем , чтобы разместить меньший прямоугольник Ri в пределах большего прямоугольника Rj, если для этого соответствовать размерность . Например, если есть четыре прямоугольника R1 (2,3), R2 (2,4), R3 (4,5) и R4 (5,7), то наибольшая возможная упаковка размером имеет размер 3, который является {R4 < - R3 < -R1} или {R4 < -R3 < - R2} Разработать алгоритм динамического программирования для определения размера упаковки для любого заданного набора прямоугольников.

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

Теперь как ученик мой вопрос, что другой подход должен должны быть приняты в связи с наличием этого предложения «Разработка алгоритма динамического программирования» Для меня это предложение не осуществление моего подхода. Я имею в виду, что единственная подсказка, которая приходит мне на ум, чтобы решить эту проблему, - это тот, о котором я упомянул.

Необходима помощь.

Я использовал следующий код;

package com.example.testing; 

import java.util.ArrayList; 
import java.util.List; 

public class RectangleTest { 
    public double height; 
    public double width; 

    public RectangleTest(double width, double height){ 
     this.width = width; 
     this.height = height; 
    } 
    public boolean canPutInside(RectangleTest r){ 
     if (this.width < r.width && this.height < r.height) 
      return true; 
     else 
      return false; 
    } 



    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     List<RectangleTest> rectangles = new ArrayList<RectangleTest>(); 
     rectangles.add(new RectangleTest(2 , 3)); 
     rectangles.add(new RectangleTest(2 , 4)); 
     rectangles.add(new RectangleTest(4 , 5)); 
     rectangles.add(new RectangleTest(5 , 7)); 
     rectangles.add(new RectangleTest(8 , 3)); 
     rectangles.add(new RectangleTest(26 , 4)); 
     rectangles.add(new RectangleTest(44 , 5)); 
     rectangles.add(new RectangleTest(5 , 1)); 
     rectangles.add(new RectangleTest(2 , 31 )); 
     rectangles.add(new RectangleTest(21 , 4)); 
     rectangles.add(new RectangleTest(6 , 51 )); 
     rectangles.add(new RectangleTest(7 , 7)); 
     rectangles.add(new RectangleTest(12 , 3)); 
     rectangles.add(new RectangleTest(31 , 4)); 
     rectangles.add(new RectangleTest(4 , 33 )); 
     rectangles.add(new RectangleTest(1, 7 )); 
     int highestPackaging = 0; 

     for(int i = 0 ; i < rectangles.size() - 1 ; i++){ 
      int count = 1; 
      for(int q = i +1 ; q < rectangles.size() ;q++){ 
       if(rectangles.get(i).canPutInside(rectangles.get(q))) 
       { 
        count++; 
       } 
      } 
      if(highestPackaging < count){ 
       highestPackaging = count; 
      } 
     } 

     System.out.println("Highest packaging size = "+ highestPackaging); 
    } 

} 

Answer 1

Это похоже на вариант longest path problem.

Предполагая, что это нормально, чтобы повернуть прямоугольники, чтобы подогнать их вместе, вы можете рассматривать каждый прямоугольник в качестве отправной точки в 2D-диаграммы рассеяния, где х (ширина) ≥ у (высота):

|        .   
    |       .   
    |       .    
    |      . A   
    |      .     
    |     . B   C 
    |     .   D   
y |    .      
    |    . E      
    |   .   F   G 
    |   .   H   I  
    |  .        
    |  .  J   K    
    | . L  M      
    | .  N   O     
    +-------------------------------------- 
        x 

Ваша задача состоит в том, чтобы найти самый длинный путь в графе, образованной эти точки (узлы), при условии ограничения, что ссылки могут быть расширены только к другим узлам с меньшим х и у координаты без обхода любых других узлов , Например, узел A может ссылаться на узлы B и D, но не на узел F, поскольку D находится в прямоугольнике, ограниченном F и A и в противоположных углах.

Свяжите каждый узел с числом, представляющим максимальную глубину пути, проходящим от этого узла, и запомните эти значения по мере продвижения. Затем ответ должен появиться довольно быстро.