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

[DJWS (...)]

這是一題可以利用dynamic programming解決的題目
推論過程不是那麼直覺
可以參考下面網址

題目 (from uva.onlinejudge.org)
http://uva.onlinejudge.org/external/101/10154.html
此題目與你所提出的問題是等價的。
兩個問題的差別僅在於載重量是否包含本身。

該題目的解法
http://online-judge.uva.es/board/viewtopic.php?f=10&t=2882
請查閱第二頁Adrian Kuegel所回覆的內容

※ 引述《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: 59.115.156.100
※ 編輯: DJWS            來自: 59.115.156.100       (04/21 00:07)
推 walker2009:跟 prob_solve 版大大的証明幾乎一模一樣 @@ 好強
→ walker2009:話說...D大是把ACM題目都背下來了嗎XD 好強
→ DJWS:我曾經有寫過這一題
→ DJWS:題號當然是記不起來  是用google搜尋題目關鍵字找到的
→ DJWS:Prob_Solve板locomotion網友的解法是LIS  應是錯誤解法
→ DJWS:Adrian Kuegel的解法與LIS是不太一樣的...
推 justdemon:我想請問 dp greedy lis 等關鍵字  是從哪裡來的？
→ justdemon:方便提供適合上手的文件嗎？  謝謝  ^^
推 locomotion:LIS是只要可以接就接上去，不能接就丟掉當前的
推 locomotion:我對LIS不熟，上面講錯了
→ DJWS:to justman: 搜尋關鍵字「CLRS」 是一本書
→ DJWS:to locamotion: 是我看錯了...歹勢 你的方法是對的 orz
→ DJWS:剛剛詳細看了一下  自己也不敢確定Adrian的方法是對的..,.