作者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