开发者

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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜