作者taro3750 (taro)
看板Prob_Solve
标题[问题] 请教关於数学几何最佳化程式的问题
时间Fri May 6 21:42:27 2011
问题：圆内求最多矩形填充的数量以及其排列情形
已知条件：
1. 矩形长宽
2. 圆形大小
求：
1. 圆内最多可填充多少矩形数目
2. 最佳的排列方式为何
其他条件：
1. 矩形不可碰触到圆形边界
2. 矩形可任意排列(不同角度)
示意图：
http://0rz.tw/L27A1
------------------------------------------------------------------------------
感觉上类似最佳化求解的问题
曾经有想过是否可以使用递回方式求解
但苦思不得其解
想请问板友是否有办法求解并提供简单的虚拟码提点小弟
感激不尽！
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.37.98.247
1F：→ tkcn:我猜是从边缘greedy吧，一开始放1~k个，所以需要做k次找最大 05/06 21:45
2F：→ tkcn:但我没办法证明 greedy 的正确性。 05/06 21:48
4F：→ taro3750:...........非常感谢你=3= 我被连结吓到了 05/06 22:06
5F：→ Pash77:把矩形 random 散落，再用一个圆慢慢圈起来? 05/07 03:24
6F：→ Pash77:感觉像有晶圆上摆放chip的感觉 05/07 03:27
7F：→ Belanice:不可碰触圆形边界的定义很模糊? 所谓不碰触的距离是多小? 05/09 00:37
8F：→ Belanice:只要用电脑就会有误差，改成不超出圆形才会比较好解 05/09 00:38
9F：→ yoco315:忘记哪边看过这问题,肯定NP的,某次培训曾经出过类似题 05/09 17:02
10F：→ yoco315:最後第一名的那个是用random解的 = =|| 05/09 17:02