Re: [問題] 一個感覺是 dynamic programming 的題目
看板Prob_Solve (計算數學 Problem Solving)作者locomotion (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
04/20 18:29, 2F
→
04/20 19:47, , 3F
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
04/20 19:50, 4F
→
04/20 19:50, , 5F
04/20 19:50, 5F
→
04/20 19:51, , 6F
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
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
04/20 21:51, 11F
→
04/20 21:52, , 12F
04/20 21:52, 12F
推
04/21 00:53, , 13F
04/21 00:53, 13F
→
04/21 10:35, , 14F
04/21 10:35, 14F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
