Влияние върху производителността
Изтегляне 1.47 Mb.
|
Свързани:
saap conspect
| Лема 1 Нека N ел. (сортирани намаляващо) с размери s1…sN могат да се подрдят оптимално в М торби.Тогава всички ел., които first fit decreasing поставя в допълнителни торби (над М) имат размер най-много 1/3.
Док. Нека елемент i е първия в торба М+1. Да докажем si <=1/3. Предполагаме si >1/3. Следва s1,…si-1 >1/3 (иначе лемата е доказана). Тогава в торби В1….ВМ има най-много ел ( нали са >1/3). Тогава в първите торби има по 1 ел. а в оставащите до М по 2 ел. Ако приемем обратното: в торба Вx има 2 ел. , а в торба By 1 el. и 1<= x < y <= M. Нека x1 и x2 са елементите в Вx и y1 е елементът в By, x1>=y1, а също и x2 >=si то: x1 +x2 >= y1 +si Значи si може да се пъхне в By, но това не беше възможно по предположение. Значи, ако si>1/3, в момента, когато го обработваме, в първите j торби има по 1 ел. а в оставащите M-j по 2 ел. Сега да покажем че няма начин всички елементи да се сложат в торби (тогава не би оставал външен <1/3) За първите j ел. няма начин 2 да се сложат в 1 торба (доказахме че в началото са по 1). Също така никой елемент до si не може да се пъхне в първите торби. Значи j торби са по 1 ел. и елементите с размери sj+1,s j+2…. S i-1 са в М-j торби.Общият брой ел. в тях е 2(М – j) Следователно, елемент si>1/3 няма начин да се вкара в първите М торби: той не може да се вкара в първите j торби, защото те съдържат по 1 ел. Не може и в оставащите M-j торби, защото в тях трябва да се появят 2(M-j) +1 елемента. Това означава в някоя торба следва да има по 3 ел (а всеки беше >1/3).Очевидно предвиж-дането в нач. беше грешно и s i <=1/3 Лема 2 Броят ел. поставени в допълнителните торби е най-много М-1 Док:Приемаме обратното: в допълнителните торби има най-малко М ел. Знаем si <= M Нека Bj е поела общо тегло Wj (1<= j <= M) Нека първите М ел. в допълнителни торби са с размер x1…xM. Тъй като елементите в първите М торби + елементите в първите М допълнителни са част от всички то: Това е невъзможно, тъй като тези N ел. са пакетирани в М торби. Следователно допълнителните торби са най-много М-1 Теорема Нека М е оптимал. брой торби за I елемента. First Fit decreasing никога не използва повече от (4М+1)/3 торби. Имаме М-1 допъл.ел.с макс.размер 1/3. Значи допълн. торби са най-много (М-1)/3. Общият бр. торби използвани в метода е : (4М –1) /3 <= (4М +1)/3 First Fit decreasing е добър и бърз подход Изтегляне 1.47 Mb. Сподели с приятели:
|