: 题目是这样的: : 给定 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)