恕删 其实loco大的解法是正解，用DP只是浪费时间，徒增时间复杂度: 依照loco大的说法是 1.Sort while not finished if 最後一个可以直接加得进去 就加进去 else 调整最佳解的结构，在结构高度相同的前提下，将总重量最佳化 (因为显然不可能让他的高度再增加) Q: 1.为何Sort? 因为你把图画出来，把每个box含自己的重量加其上box之重量写出来就会发现， 其实最佳解必定为一个capacity由小->大的sequence 2.为何抽掉最重的box? 所谓抽掉最重的box的意思: (i)Case:第i box重量比考虑前i-1的box的最佳解结构中最重的box还要重， 则我们不变动最佳解(就是抽掉第ibox) (ii)Case:第i box重量比考虑前i-1的box的最佳解结构中最重的box还要轻， 则我们将i-1结构中最重的box抽掉，并且在最後加入第i box(为何 一定加得进去?考虑在i-1最佳解中的最後一个box k之capacity c[k] 以及第i box的capacity c[i],因为c[k]>w[1]+w[2]+...+w[max]+w[k] 其中w[1],w[2]是代表最佳解中的第一个box 第二个box的重量，而 w[max]是其中最大者。又因为w[i]<w[max]且i>k=>c[i]>c[k]>w[1]+w[2] +...+w[max]+...+w[k]>w[1]+w[2]+...+w[i]+...+w[k] 以下为证明在各个阶段如此做能够求得最佳解(高度最高的前提下，重量和最小的 box sequence): i=1 的时候显然能够加入第一个box，而此时高度为1的box sequence就是最佳解。 设i=k-1的时候命题成立(假设用以上方法求出的是最佳解:不失一般性设为 x=<box[1],box[2],...,box[s]>,代表在前k-1个箱子中，所有的sequence最高可能 高度为s,且重量是高度为s中最轻的,in other words: w[1],...,w[s]乃最轻的重量总和) i=k的时候 case 加得进去: 则加进去形成length是s+1的最佳解 显然不可能再形成更长的length不然就和假设自相矛盾,唯一有 可能有问题的是会不会存在一个sequence y+box[k] 和考虑k-1箱子之最佳解x=<box[1],box[2],...,box[s]>+box[k] 不全相同，长度相同且重量和较轻。 显然如果存在的话y和原来sequence x的长度相同且y重量较轻， 就又和归纳假设矛盾。所以在此case命题成立(在此 状况下依照上面的方法会求到重量最轻且长度最长的box sequece) case 加不进去:(c[k]<weight(x)+w[k]) subcase:若是w[k]<w[max]，依照方法会把box[max]丢掉，将box[k] 放在最下==>此法求出的box sequence z=<box[1],box[2], ...,box[s],box[k]> 验证长度: [矛盾]:假设用此法求出的解长度不是最长的合法sequence 代表存在一个合法sequence y其长度>=s+1(因为z长=x长=s) ==>若y中无box[k]，则显然和归纳假设矛盾 若y中有box[k]，则存在y'=y-box[k],y中只含有前面k-1的 箱子，且y'长度=y长度-1=s+1-1=s=x长度，且y'也合法 ==>y'合法:c[k]>=weight(y')+w[k],又我们在加不进去的 状况下所以，c[k]<weight(x)+w[k] ==>weight(y')<=c[k]-w[k]<weight(x)，这个和我们的归纳假 设x是考虑到box k-1中重量最小者矛盾，所以长度 必定<=s，长度成立 验证重量: [矛盾]假设weight(z)不是长度s中重量最小的sequence ==>存在一条y使得weight(y)<weight(z)，且y长=z长=s ==>1.若是y中无box[k]，则y是一条只考虑前k-1box且长度为 s的sequence. ==>weight(y)<weight(z)=weight(x)-w[max]+w[k]< weight(x)，和归纳假设矛盾 2.若是y中有box[k]，又y长=s，代表y的sequence是由 x-box[j]+box[k] 任意j=1 to s 形成的 又我们知道z中是将w[max]带换掉所以存在有j使得 weight(y)=weight(x)-w[j]+w[k]<weight(x)-w[max]+w[k]= weight(z) ==>w[j]>w[max] 矛盾，所以不可能 依照以上两点在此subcase中使用此方法会求得最佳解 subcase:若是w[k]>=w[max]，此时我们不变动最佳解，也就是说此 方法求出来的解结构z=x 因为加不进去所以显然长度不可能在更长 因为w[k]比原结构中的重量都大，所以不用考虑box[k] 重量就会是最佳 依照以上，此subcase中，命题成立 以上涵括所有状况，所以保证induction step成立，by induction 命题成立 所以意思就是，只要我们保证每个阶段我们求得的是长度最长的前提下的重量 最小结构，最後求出来的就会是最佳解，而且此方法正确无误。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 203.222.23.95 ※ 编辑: keeperkai 来自: 203.222.23.95 (04/23 02:03)