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

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

※ [本文轉錄自 C_and_CPP 看板]

作者: walker2009 (誰人未嘗自以為) 看板: C_and_CPP
標題: [問題] 一個感覺是 dynamic programming 的題目
時間: Tue Apr 20 14:12:20 2010

朋友問了我一個題目 我感覺是 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
--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.32.236.211
→ aks4751:單看問題的話，我覺得這比較像NPC問題(0-1背包問題)
→ aks4751:就算存在DP解可能也很慢
→ aks4751:我好像搞錯了...請刪除吧
→ walker2009:XD
→ walker2009:以最下面那個箱子而言 的確上面感覺像是 0-1背包問題
→ walker2009:但以第二個箱子而言 上面又是另外一個 0-1背包問題
→ walker2009:提供了我一個思考方向 感恩!