Блог

Я нахожу алгоритм слияния пакетов

 Algorithm(I, X) {
    S is empty;
    for all d, Ld list of items having width 2^d;
    while X > 0 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.”
}
  

У меня есть несколько вопросов об алгоритме.
что такое Ld 1?
почему мы отбрасываем Ld, когда у него может быть одна монета, значение которой = minwidth, когда r

Ld 1 на самом деле

L_{d 1}

Смотрите здесь (Быстрый алгоритм для оптимальных кодов Хаффмана с ограниченной длиной)

Это означает запись списка в местоположении d 1 . Итак, если d == 5, это шестая запись списка.