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

看板C_and_CPP作者DJWS (...)時間15年前 (2010/04/20 23:58)推噓4(4推 0噓 9→)

留言13則, 4人參與討論串3/3 (看更多)

這是一題可以利用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

04/21 00:36, , 1^F

04/21 00:36, 1^F

→

walker2009

04/21 00:37, , 2^F

04/21 00:37, 2^F

→

DJWS

04/21 09:17, , 3^F

04/21 09:17, 3^F