推 walker2009:感謝回應! 乍看之下還不太能理解...待我思考幾分鐘先 04/20 18:28
→ walker2009:還附上證明了 Orz 實在太麻煩大大了 04/20 18:29
→ ADF:La Lb會隨箱子次序調換而改變.. 04/20 19:47
的確，這一環忘了說(怪不得常常被老闆念 囧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，當然裝的下)
這個證明在檢查的時候，應該是由最上層往最下層檢查
所以這個性質還是沒有問題的
推 walker2009:照這演算法下去coding 程式已經AC...但小弟資質駑鈍 04/20 19:50
→ walker2009:還在思考為什麼這樣會是正確的 04/20 19:50
→ walker2009:而且這作法好像是 greedy...XDDD 所以根本不是 DP 04/20 19:51
→ walker2009:至少有一最佳解是載重量由小到大這個我可以理解了 04/20 19:53
→ walker2009:但為什麼在超過當前載重量時是拿上面最重的而不是其他 04/20 19:53
→ walker2009:關於這點還在想辦法證明中 囧rz 04/20 19:54
推 walker2009:應該是說 要怎麼確定拿掉的箱子不會在最佳解裡 04/20 20:09
敝人最大的特點之一就是表達能力有點差...所以不是你資質駑鈍啦
他是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)
推 walker2009:Orz太感謝了!有些地方還要再思考一會!但大方向都知道了 04/20 21:51
→ walker2009:馬上去wiki一下什麼是strongly NP-Hard XDDD 學藝不精 04/20 21:52
推 walker2009:C_and_Cpp 版有大大回文了! greedy解似乎不對,好像要DP 04/21 00:53
→ locomotion:DP是O(n^2)，這個方法是O(n logn)，沒錯喔 04/21 10:35