: 題目是這樣的: : 給定 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 的確，這一環忘了說(怪不得常常被老闆念 囧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，當然裝的下) 這個證明在檢查的時候，應該是由最上層往最下層檢查 所以這個性質還是沒有問題的 敝人最大的特點之一就是表達能力有點差...所以不是你資質駑鈍啦 他是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)