上一篇太长，以下是我根据loco大的说法写出来的演算法， 希望各位指正: input w[],c[]//重量矩阵 耐重矩阵 data structures: int m[]:用来记录考虑前i box的时候的可能最高高度 box s[]:一个纪录在考虑前i box的时候高度最高前提下，重量最小的 解中含有的box set int maxindex:纪录当前解结构中重量最大的box的index int weightofset:纪录当前解结构的重量总和 想法: 先排序依照capacity的Increasing order，从只考虑第一个箱子开始， 最佳解就是第一个箱子，并且依照loco大的想法运作，依序球出s[n],m[n] 当然s,m不用阵列也可以，因为演算法只会用到上一次解结构的内容， 只是这样写比较清楚。 m[i]= m[i-1]+1, c[i]>=w[i]+weightofset m[i-1], otherwise s[i]= s[i-1]+box[i], c[i]>=w[i]+weightofset otherwise s[i-1]+box[i]-box[maxindex],w[i]<w[maxindex] s[i-1],otherwise Algo: Sort(c[],w[]) m[1]=1 s[1]=box[1] maxindex=1 weightofset=w[1] for i= 2 to n if c[i]>=w[i]+weightofset m[i]=m[i-1]+1 weightofset=weightofset+w[i] s[i]=s[i-1]+box[i] if w[i]>w[maxindex] maxindex=i else m[i]=m[i-1] if (w[i]>=w[maxindex]) s[i]=s[i-1] else weightofset=weightofset+w[i]-w[maxindex] s[i]=s[i-1]+box[i]-box[maxindex] maxindex=getmaxindex(s[i],w[])//这里偷懒 本人第一次po文，也并非专业人士，希望各位大大可以"温和"一点指正(鞭)我XD --

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