[問題] 請教關於數學幾何最佳化程式的問題

[taro3750 (taro)]

問題：圓內求最多矩形填充的數量以及其排列情形

已知條件：

1.  矩形長寬
2.  圓形大小

求：

1.  圓內最多可填充多少矩形數目
2.  最佳的排列方式為何


其他條件：

1.  矩形不可碰觸到圓形邊界
2.  矩形可任意排列(不同角度)

示意圖：http://0rz.tw/L27A1

------------------------------------------------------------------------------

感覺上類似最佳化求解的問題

曾經有想過是否可以使用遞迴方式求解

但苦思不得其解

想請問板友是否有辦法求解並提供簡單的虛擬碼提點小弟

感激不盡！

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.37.98.247
→ tkcn:我猜是從邊緣greedy吧，一開始放1~k個，所以需要做k次找最大
→ tkcn:但我沒辦法證明 greedy 的正確性。
→ tkcn:看了http://goo.gl/SDDoO 之後, 我不認為這題會有簡單的解
→ taro3750:...........非常感謝你=3= 我被連結嚇到了
→ Pash77:把矩形 random 散落，再用一個圓慢慢圈起來?
→ Pash77:感覺像有晶圓上擺放chip的感覺
→ Belanice:不可碰觸圓形邊界的定義很模糊? 所謂不碰觸的距離是多小?
→ Belanice:只要用電腦就會有誤差，改成不超出圓形才會比較好解
→ yoco315:忘記哪邊看過這問題,肯定NP的,某次培訓曾經出過類似題
→ yoco315:最後第一名的那個是用random解的 = =||