作者justdemon (人生的轉捩點)
看板C_and_CPP
標題Re: [問題] 一個感覺是 dynamic programming 的題目
時間Tue Apr 20 16:54:27 2010
提供小弟思考之後的淺見 有錯煩請指教
1. 建一個list 照重量排序
2. 把載重最大的放最下面
3. 把重量在可容許的最大載重以下的最重的箱子放上，並更新剩餘容許載重
4. 直到無法在放上任何箱子，紀錄最高層數，並取下最上層的箱子，再放上
次重的箱子，直到無法繼續，再次紀錄層數。(一直遞迴...)
※ 引述《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: 140.112.101.114
1F：推 walker2009:感謝回應, 但經過思考, 把載重量最大的放最下面這一步 04/20 17:02
2F：→ walker2009:似乎就已經不正確了 04/20 17:02
3F：→ walker2009:試考慮兩個箱子 一個載重量最大 另外一個只比他少1 04/20 17:03
4F：→ walker2009:但載重量最大的那個很輕, 另外一個非常重 04/20 17:03
5F：→ walker2009:如果把載重量最大的放最下面 非常重的那個就得放上面 04/20 17:04
6F：→ walker2009:使得之後的載重量變得非常小 04/20 17:04
7F：→ justdemon:原題意看起來 載重量不包含自己吧?? 04/20 17:21
8F：→ justdemon:如果包含自己 那最多就是多一層遞迴 第一層無法直接 04/20 17:22
9F：→ justdemon:決定 應該還可以延用 04/20 17:22
10F：推 walker2009:包不包含其實可以很輕鬆轉換,但不管包不包含應該都無法 04/20 17:27
11F：→ walker2009:直接決定第一層 04/20 17:27
12F：→ mantour:這篇的方法等於把所有允許疊法試過一遍了吧 04/20 17:58
13F：推 walker2009:似乎是XD 時間上應該過不了 04/20 17:59
14F：→ walker2009:依然想不到跟 subproblem 之間的關係...好悶 04/20 18:00
15F：→ walker2009:是說也還沒確定是 DP 解啦...搞不好有更好的解法 04/20 18:00