What does this line of code mean in this package-merge algorithm?
I find an algorithm Package-Merge
Algorithm(I, X) {
S is empty;
for all d, Ld list of items having width 2^d;
while X > 0 开发者_C百科loop
minwidth = the smallest term in diadic expansion of X;
if I=0 then //is empty
return “No solution.” ;
else
d=the minimum such that L is not empty;
r=2^d;
if r > minwidth then
return “No solution.”
else if r = minwidth then
Delete the minimum weight ;
X= X - minwidth ;
end if
Pd+1=PACKAGE(Ld) ;
discard Ld ;
Ld+l=MERGE(pd+1,Ld+1);
end if
end loop
return “S is the optimal solution.”
}
I have some question about algorithm. what is Ld+1? why we discard Ld when it maybe have one coins that its value=minwidth when r
Ld + 1 is actually
Ld+1
See here (A Fast Algorithm for Optimal Length-Limited Huffman Codes)
It means the list entry at the location d+1
. So if d == 5, it's the sixth list entry.
精彩评论