java - 动态编。 Algo 矩形包装

Question

我有一个作业问题

You are given a set of n 2-dimensional rectangles. You need to find a maximum possible packaging of subset of rectangles. By packaging we mean to place a smaller rectangle Ri within a larger rectangle Rj if dimension conform for doing so. For example if there are four rectangles R1(2,3),R2(2,4),R3(4,5) and R4(5,7) then the largest possible packaging is of size 3 which is {R4 <- R3 <-R1} or {R4 <-R3 <- R2} Design a dynamic programming algorithm for finding the largest size of packaging for any given set of rectangles.

我将通过比较尺寸并计算一个矩形的尺寸是否较小以便可以打包来解决这个问题。

现在作为一名学习者，我的问题是由于这句话的存在必须采取什么不同的方法“设计动态规划算法” 对我来说，这句话不会影响我的方法。我的意思是，我想到的解决这个问题的唯一线索就是我提到的那个。

需要帮助。

我使用了下面的代码；

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 的一个变体.

假设可以旋转矩形以将它们组合在一起，您可以将每个矩形视为二维散点图中的一个点，其中 x(宽度)≥ y(高度):

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

你的任务是在这些点(节点)形成的图中找到最长的路径，受制于链接只能延伸到其他x和y较小的节点的约束 协调而不绕过任何其他节点。例如，节点 A 可以链接到节点 B 和 D，但不能链接到节点 F，因为 D 位于由 F 和 A 对角包围的矩形中。

将每个节点与表示从该节点延伸的路径的最大深度的数字相关联，并在进行时记住这些值。答案应该会很快出现。