PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者 (locomotion)時間14年前 (2010/04/20 18:13), 編輯推噓5(5推 0噓 9→)
留言14則, 3人參與, 最新討論串2/12 (看更多)
: 題目是這樣的: : 給定 n 個箱子, 每個箱子有其自己的 重量 以及 載重量 : 現在要將箱子一層一層往上疊, 順序不拘 : 每個箱子上方所有的重量加起來不能超過自己的載重量 : 試問, 最高可以疊到幾層? 換個方向思考吧，不要先放最下面的那一個 先放最上面的那一個呢? 1.先將所有箱子依載重量由小到大排 (Sorting:O(nlogn)) 2.依載重量由小到大放進list a.如果累積的重量比當前箱子的載重量小，將箱子放進list b.如果累積的重量超過當前箱子的載重量 將目前list中最重的箱子拿走 為什麼這樣是對的? 假設在最佳解中，箱子a的載重量(Ca)比箱子b(Cb)大，可是他排在比較高的高度 用La代表箱子a在此位子的負重，Lb為箱子b在此位子的負重 因為Cb<Ca，Lb<Cb，所以Lb<Ca (b都已經擺在a下面了...所以La<Cb) 所以可以調換這兩個箱子的順序 將所有不符合此順序的箱子調整之後 則最下層的箱子載重量一定是疊起來的箱子中最大的 因此，一定至少有一最佳解，載重量是由小到大的(從高層到低層看來) 也因為如此，考慮這個性質，我們只需要考慮這個情況就好了 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.73.99
推
04/20 18:28, , 1F
感謝回應! 乍看之下還不太能理解...待我思考幾分鐘先
04/20 18:28, 1F
→
04/20 18:29, , 2F
還附上證明了 Orz 實在太麻煩大大了
04/20 18:29, 2F
→
04/20 19:47, , 3F
La Lb會隨箱子次序調換而改變..
04/20 19:47, 3F
的確，這一環忘了說(怪不得常常被老闆念 囧rz) 這個證明一開始應該假設只有兩個箱子不在順序上才是... 以箱子A為例，重量為WA，負重為LA，載重量為CA 先假設AB之間只有隔著箱子C 先講AB的部分 假設AB交換，則LB' = LA-WA+WB 因為LB包含LA+WB，所以LB'<CB (原先B要承載的重量是A上面的東西加上ABC 現在只需要裝A原先上面的東西跟自己，負擔當然比較小) LA' = LB，之前說過了LB<=CB<CA (既然A可以裝的比較重，沒道理B可以裝的A裝不下吧) 假設AB之間只隔一個箱子C，已知LC<CC LC' = LC-WA+WB 1.如果A比較重或者跟B一樣重，那新的負重對C來說一定沒問題 2.如果LC'>CC，這就代表C的載重量比B小，那就把C再跟B換就可以了 (B可是可以乘載箱子A上的東西跟ABC的重量的， 現在不裝A了C還裝不下，可見C的載重量一定比B小) 則LC'' = LC-WA-WB，所以LC''<LC (再交換之後，C現在在AB上頭了，所以這次AB的重量都扣掉了，C這次一定裝得下了) 此時LB'' = LA - WA + WB +WC，因為LB包含LA+WB+WC，所以LB''<CB (B本來就是ABC都裝得下的，現在少了A，當然裝的下) 這個證明在檢查的時候，應該是由最上層往最下層檢查 所以這個性質還是沒有問題的
推
04/20 19:50, , 4F
照這演算法下去coding 程式已經AC...但小弟資質駑鈍
04/20 19:50, 4F
→
04/20 19:50, , 5F
還在思考為什麼這樣會是正確的
04/20 19:50, 5F
→
04/20 19:51, , 6F
而且這作法好像是 greedy...XDDD 所以根本不是 DP
04/20 19:51, 6F
→
04/20 19:53, , 7F
至少有一最佳解是載重量由小到大這個我可以理解了
04/20 19:53, 7F
→
04/20 19:53, , 8F
但為什麼在超過當前載重量時是拿上面最重的而不是其他
04/20 19:53, 8F
→
04/20 19:54, , 9F
關於這點還在想辦法證明中 囧rz
04/20 19:54, 9F
推
04/20 20:09, , 10F
應該是說 要怎麼確定拿掉的箱子不會在最佳解裡
04/20 20:09, 10F
敝人最大的特點之一就是表達能力有點差...所以不是你資質駑鈍啦 他是Greedy沒錯，可是因為有拿掉箱子這一步，才讓他可以產生最佳解 1.如果沒有任何箱子需要拿掉，這當然是最佳解，n個箱子疊n層，完美! 2.已經堆了k層，要拿掉一個箱子 你說那不堆這第K個箱子先堆別的? 既然K在這裡都撐不住了，在後面就更不可能了 既然要拿掉一個，箱子的重要性都一樣，那當然是拿最重的那一個 (如果箱子的重要性不一樣，這個問題就是Strongly NP-Hard) 如果是問為什麼只拿掉一個就好 箱子由上到下是A-B-C，你現在要再把A-B-C放到D上面 假設最極端的情況是A-B-C的總重量其實已經等於D的載重了 如果最重的那一個是D，那D拿掉目前堆的箱子還是A-B-C，沒有人超過載重 如果最重的是C，則A-B-D的總重比A-B-C小，現在就放得下了 (提醒一下，箱子是依負載量疊的，D的負載量等於或大於C) 而且因為A-B-D比較小，對後面的箱子來說也是比較有利的 ※ 編輯: locomotion 來自: 140.113.73.99 (04/20 21:11)
推
04/20 21:51, , 11F
Orz太感謝了!有些地方還要再思考一會!但大方向都知道了
04/20 21:51, 11F
→
04/20 21:52, , 12F
馬上去wiki一下什麼是strongly NP-Hard XDDD 學藝不精
04/20 21:52, 12F
推
04/21 00:53, , 13F
C_and_Cpp 版有大大回文了! greedy解似乎不對,好像要DP
04/21 00:53, 13F
→
04/21 10:35, , 14F
DP是O(n^2)，這個方法是O(n logn)，沒錯喔
04/21 10:35, 14F
‣ 更多 locomotion 的文章
文章代碼(AID): #1BpNuj0n (Prob_Solve)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 2 之 12 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共12篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 locomotion 的文章
文章代碼(AID): #1BpNuj0n (Prob_Solve)