征求一个（计算一个矩形内是否满足多个矩形的排列）的算法

2014-07-27 20:03:25 +08:00
 twor2
题目：计算一个矩形内是否满足多个矩形的排列
图示：



输入1：大矩形的长宽，里面小矩形的种类数量（这个案例中是3），每个小矩形类型的长宽和数量
输出1：小矩形是否能全部排列在大矩形内部（当然不许折叠重合）

语言不限！

设立啥奖品好哩？
4090 次点击
所在节点    程序员
15 条回复
FuryBean
2014-07-27 20:11:35 +08:00
假设每个Rect的保存方式是left、top、right、bottom。

1. 遍历所有的小矩形，保存所有小矩形中的最小left、最小top、最大right、最大bottom。
2. 把第一步保存的结果与大矩形的left、top、right、bottom比较，大矩形的left、top必须小于保存的矩形的left、top，right、bottom则是大于。

Done。
FuryBean
2014-07-27 20:13:40 +08:00
刚发现看错题目了，原来小矩形的位置是不知道的，这种没算过，请忽略我的答案吧。
thisisvoa
2014-07-27 20:48:49 +08:00
关注中，正在研究canvas标签的矩阵缩放
Kabie
2014-07-27 20:50:55 +08:00
小矩形是不能转动的吧。。。？
sennes
2014-07-27 20:58:13 +08:00
题目很有趣 想用python试试!
xjx0524
2014-07-27 21:39:42 +08:00
数据规模呢？
waltwang
2014-07-27 21:47:05 +08:00
去年实现过类似的，动态规划习题...用的是C++
iloahz
2014-07-27 22:04:42 +08:00
直观感觉只能搜啊……
c742435
2014-07-27 23:09:54 +08:00
一下子想到texture packer了
est
2014-07-27 23:47:18 +08:00
这不就css sprite如何摆图标嘛。。。
htedsv
2014-07-28 00:53:42 +08:00
如果所有尺寸的值域是有限集合就是高维状态的动态规划，否则是NP或者PSPACE问题。
flyee
2014-07-28 09:30:50 +08:00
http://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu
twor2
2014-07-28 10:02:31 +08:00
@sennes 欢迎试一下
twor2
2014-07-28 10:03:06 +08:00
@htedsv 有点高大上，谢谢你的回答。
twor2
2014-07-28 10:10:08 +08:00
@flyee 已保存

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/124751

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX