[問題] 疊烏龜問題

[hatasum (我很可愛)]

恩...題目很簡單 但是我始終想不出來要怎麼用程式寫出來...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)
推 varg:用dfs那種作法應該可吧?
推 senjor:用HillClimbing直接爬，至少可以很快找出解 @@
→ hatasum:....其實data有100組....
→ senjor:不如把DATA放到網頁上，讓大家玩一玩吧 XD
推 motai:最下面(第一隻)放編號1 體重80 載重100  2.3.4疊在上面3隻共
→ motai:80   那跌最上面的第5隻不是應該20以下嗎  妳說15以下
→ motai:我的第一句的編號1打錯   是10
→ hatasum:真正的負重是min(排出來後剩餘的負重, 最上層的負重)
→ hatasum:我這例子是取4的負重是15  所以min(20,15)