动态推进Algo矩形封装
动态推进Algo矩形封装
提问于 2015-04-22 10:33:53
我有个作业问题
给出一组n维矩形.您需要找到矩形子集的最大可能封装。通过打包，我们意味着将一个较小的矩形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);
}
}回答 1
Stack Overflow用户
回答已采纳
发布于 2015-04-22 12:41:16
这看起来像最长路径问题的变体。
假设可以旋转矩形以使它们结合在一起，您可以将每个矩形看作二维散点图中的一个点，其中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在相对角落的矩形中。
将每个节点与表示从该节点延伸的路径的最大深度的数字关联起来，并在进行过程中回溯这些值。答案应该很快就会出现。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/29794841
复制相关文章
相似问题
腾讯云开发者
