[問題] 一個感覺是 dynamic programming 的題目

[walker2009 (誰人未嘗自以為)]

朋友問了我一個題目 我感覺是 dynamic programming

但又不太確定 (因為我找不到最後的解跟 subproblem 之間的關係 Q_Q)



題目是這樣的:


給定 n 個箱子, 每個箱子有其自己的 重量 以及 載重量

現在要將箱子一層一層往上疊, 順序不拘

每個箱子上方所有的重量加起來不能超過自己的載重量

試問, 最高可以疊到幾層?



我一開始想法是, 最大載重量的放最下層

之後第 k 層 會選擇 下面 k-1 個箱子中

 min(剩餘載重量最大的那一個 - 第i個箱子的重量, 第i個箱子的載重量) 最大的那個
    for all i = 1 to n and i'th box has not been used

但後來 verify 發現這想法有錯誤, 而且感覺好像有點偏 greedy



每次想 dp 的題目我都會不自覺往 greedy 那邊想過去

不知道該如何培養對 dp 的敏銳度 Orz 希望有概念的大大能指導一下

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.236.211
※ 編輯: walker2009      來自: 114.32.236.211       (04/20 14:13)
→ Dannvix:有 prob_solve 板唷
→ walker2009:喔喔喔喔! 3q
※ walker2009:轉錄至看板 Prob_Solve                                04/20 14:24
→ walker2009:囧 去那邊發現人氣 0
推 holymars:n的值是多少？
→ walker2009:n 不固定 @@ 最大可能到 10000
推 holymars:最大10000的話表示最多是n^2解了(愣
→ holymars:應該說，這題多半是n^2　題目的數字有時侯也是一種提示XD
→ walker2009:喔喔~ n^2 logn 沒機會嗎~
推 ledia:載重量最大多少 ?
→ walker2009:看了一下~ 載重量跟 重量 都無限制範圍
→ walker2009:努力往 n^2 logn 方向思考中 Orz
→ tkcn:n^2 log(n) 不是比 n^2 還大嗎
推 zerodevil:logn通常小到可以無視XD
推 zerodevil:O(n^2)的dp大概會像這樣:
→ zerodevil:dp(i,j):=從箱子i~n挑j個疊起來,這j個箱子的最小重量和
→ zerodevil:當然箱子要經過某個方法排序 先提示到這裡XD
→ rephansu:1Kgw的箱子載重量1Tgw,那問這問題不就沒意義了
→ utomaya:是我誤解題意嗎? 這題不是很簡單嗎? 就把箱子重量排序
→ utomaya:從最小重量的箱子開始加 加到超過重量前的最輕一個箱子止
→ walker2009:嗯...應該是誤解題意了
→ walker2009:重量輕的可能載重量大, 重量重的可能載重量小
→ walker2009:prob_solve 版有大大幫解出來了...只是我還看不懂原因
→ bleed1979:可以說明題號多少嗎？
→ walker2009:沒有題號啦XDD 是朋友問我的
→ walker2009:咦@@ 下面有大大回了一篇跟這篇很像的題目
→ walker2009:通盤了解以後發現zerodevil大的就是正解XD後知後覺啊我