作者chrisdar (克里斯)
看板Prob_Solve
標題Re: [問題] 如何解 池塘邊的木頭 問題
時間Fri Nov 7 12:36:56 2008
※ 引述《Fenikso (我是蜜蜂~)》之銘言：
: ※ 引述《ledia (下班後才下棋)》之銘言：
: : ◆ From: 140.112.30.54
: : 推 chrisdar:忘記說 全都是整數 11/06 07:29
: : 推 Fenikso:為什麼可以保證第i根要擺在第i+1根前面? 11/06 21:25
: : 推 Fenikso:這樣不一定會最好 11/06 21:27
: : 推 yoco315:其實我覺得這提用 simplex 最好.. 11/07 04:33
: : → yoco315:數字範圍還可以是實數... @@" 11/07 04:33
: : 推 chrisdar:Fenikso 我試過把順序洗亂下去解線性規畫 值都比1500大 11/07 08:08
: 可能是你洗的太亂了
: 把Yi相同的那些重排試試看
: : 推 chrisdar:to yoco315 您的意思是我把45頂點的簡單型壓成一維? 11/07 08:17
: : 推 chrisdar:to Fenikso 或許是限制式的問題導致 11/07 08:25
: 那我舉個例子好了
: 寬度100
: Yi = {3, 4}, H = {80, 2}
: 你覺得該怎麼移?
: 最佳解應該是把短的那根(Yi[1])搬到頭才對喔
我把資料又重新排序了 用木頭的中點來排序
Yi[45] = { 60, 78,130,151,155,224,236,238,246,260,352,356,394,409,419,
429,432,430,440,446,453,452,464,464,480,517,523,547,634,709,
712,712,712,712,712,712,713,713,713,713,713,718,724,725,725 }
H[45] = { 13, 4, 10, 4, 4, 7, 7, 5, 3, 4, 3, 5, 2, 4, 3,
5, 6, 23, 3, 3, 2, 5, 2, 4, 7, 3, 23, 7, 2, 19,
16, 16, 16, 16, 16, 16, 15, 15, 15, 15, 15, 10, 4, 2, 2 }
Solution: 1492
Yo[45] = { 60, 78,130,151,155,224,234,241,246,260,352,356,394,409,413,
416,421,427,450,453,456,458,464,466,480,487,490,513,520,522,
541,557,573,589,605,621,637,652,667,682,697,712,722,726,728 }
確實沒考慮到您所提到的問題 目前的值 1492 有變小了 不過這真的是最小了嗎?
目前還是沒想到有效的演算法，如果有就可以花時間把全部的排列都列出來去解，
目前都還是套用之前線性規畫的模型(不更換次序的原則下)去解的。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.195.68.196
1F：推 Fenikso:這題除了A*之外我沒什麼好想法.. 11/07 14:33