[問題] 一個感覺是 dynamic programming 的題目
朋友問了我一個題目 我感覺是 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)
→
04/20 14:20, , 1F
04/20 14:20, 1F
→
04/20 14:21, , 2F
04/20 14:21, 2F
※ walker2009:轉錄至看板 Prob_Solve 04/20 14:24
→
04/20 14:25, , 3F
04/20 14:25, 3F
推
04/20 14:30, , 4F
04/20 14:30, 4F
→
04/20 14:32, , 5F
04/20 14:32, 5F
推
04/20 14:33, , 6F
04/20 14:33, 6F
→
04/20 14:33, , 7F
04/20 14:33, 7F
→
04/20 14:37, , 8F
04/20 14:37, 8F
推
04/20 14:44, , 9F
04/20 14:44, 9F
→
04/20 14:45, , 10F
04/20 14:45, 10F
→
04/20 14:46, , 11F
04/20 14:46, 11F
→
04/20 15:17, , 12F
04/20 15:17, 12F
推
04/20 15:19, , 13F
04/20 15:19, 13F
推
04/20 15:21, , 14F
04/20 15:21, 14F
→
04/20 15:22, , 15F
04/20 15:22, 15F
→
04/20 15:23, , 16F
04/20 15:23, 16F
→
04/20 15:57, , 17F
04/20 15:57, 17F
→
04/20 17:43, , 18F
04/20 17:43, 18F
→
04/20 17:44, , 19F
04/20 17:44, 19F
→
04/20 17:53, , 20F
04/20 17:53, 20F
→
04/20 17:53, , 21F
04/20 17:53, 21F
→
04/20 19:52, , 22F
04/20 19:52, 22F
→
04/20 23:21, , 23F
04/20 23:21, 23F
→
04/21 00:29, , 24F
04/21 00:29, 24F
→
04/21 00:31, , 25F
04/21 00:31, 25F
→
04/21 01:00, , 26F
04/21 01:00, 26F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 3 篇)：