作者hatasum (我很可愛)
看板C_Sharp
標題[問題] 疊烏龜問題
時間Thu Oct 30 23:05:33 2008
恩...題目很簡單 但是我始終想不出來要怎麼用程式寫出來...XD
假設每隻烏龜都有兩個數據 自己的體重 和 自己最多能乘載的重量
現在有100組烏龜 每隻烏龜都有編號(0 1 2...99)
去作堆疊
請用程式找出 最多隻烏龜的排法(如果最多隻烏龜排法有很多種 那就都要列出來)
Output: 最多疊n隻 排列順序為xxxxxxx
=============================================================================
想了很久...XD但是始終找不到邏輯
我之前的一個錯誤做法，大家可以參考
=========================================================
第一隻放"最大乘載量"的烏龜
他的上面那隻放"max(第一隻乘載量-第二隻重量)"的那一隻
=========================================================
我用這邏輯去寫 也寫出來了 但是發現問題一大堆!!!
ex:
假設用這邏輯 我找出編號順序為 1=>2=>3=>4(也就是編號1是這data中乘載最大的)
假設經過這1234的排列後 最上面現在只能再放15g以下的烏龜
假設編號1體重10g 可載重100g
編號2+3+4 體重80g 但因為乘載關係 4的上面只能再放15g
現在有第5隻烏龜 重量15g 可載重90g
Q1: 1234 這時候也有另一個選擇了 5234 (最大乘載量放第一個不一定對了!!)
Q2:
選擇1234 4的上面只能再放15g 而5重量20g 所以不能放
選擇5234 4的上面只能再放10g 但是1的重量剛好可以放 所以就變成 52341.....
ANS:一開始的邏輯是錯的...= =最下面到底要放誰???
============================================================================
目前我還在想 聽說有人想出來了XD
但是我總覺得這題目真的可以做出來嗎...??
^^"如果有什麼結果我會再po文的 也歡迎大家想想這題目 討論看看
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.0.217.51
※ 編輯: hatasum 來自: 123.0.217.51 (10/30 23:09)
1F：推 varg:用dfs那種作法應該可吧? 10/31 01:14
2F：推 senjor:用HillClimbing直接爬，至少可以很快找出解 @@ 10/31 09:32
3F：→ hatasum:....其實data有100組.... 10/31 21:54
4F：→ senjor:不如把DATA放到網頁上，讓大家玩一玩吧 XD 11/01 01:00
5F：推 motai:最下面(第一隻)放編號1 體重80 載重100 2.3.4疊在上面3隻共 11/03 06:46
6F：→ motai:80 那跌最上面的第5隻不是應該20以下嗎 妳說15以下 11/03 06:47
7F：→ motai:我的第一句的編號1打錯 是10 11/03 06:48
8F：→ hatasum:真正的負重是min(排出來後剩餘的負重, 最上層的負重) 11/05 00:33
9F：→ hatasum:我這例子是取4的負重是15 所以min(20,15) 11/05 00:33