Title: I екземпляр
Author: Валери Цеков
Last saved by: Kristiyan Haralambiev

Валери Стефанов Цеков

гр. Грамада

ОПИСАНИЕ НА ИЗПОЛЗВАНИЯ АЛГОРИТЪМ И НА РЕАЛИЗИРАЩАТА ГО ПРОГРАМА FENCE
Ще започнем с кратко описание на използваното машинно представяне на данните:
- Четенето на входните данни от текстовия файл OGRADA.INP се осъществява с помощта на входния поток ifs.
- Записването на изходните данни в текстовия файл OGRADA.OUT се осъществява с помощта на изходния поток ofs.
- В променливите n, m и k се съхранява съответно броят на редовете и на стълбовете в правоъгълната мрежа и броят на дърветата в горския участък.
- В i-тите елементи на едномерните масиви y[ ] и x[ ] се съхраняват съответно номерът на реда и номерът на колоната, в които се намира i-тото дърво на горския участък.
- В i-тите елементи на едномерните масиви c[ ] и l[ ] се съхраняват съответно цената на i-тото дърво на горския участък и броят на метрите ограда, които могат да се направят от това дърво.
- По време на работа на програмата FENCE в променливите numc и sumc се съхраняват съответно броят и сумарната цена на отрязаните дървета от намереното до момента най-добро (в съответсвие с условието) решение на задачата, а в едномерния масив tr[ ]– номерата на самите отрязани дървета. Накрая от тези променливи взимаме данните за окончателното решение на задачата, които се извеждат във файла OGRADA.OUT.
Следва описанието на самия алгоритъм и на реализиращата го програма FENCE:
1. Отварят се текстовите файлове OGRADA.INP и OGRADA.OUT, които са свързани съответно с входния поток ifs и изхoдния поток ofs (функция main).
2. Прочитат се първите три числа от файла OGRADA.INP и се записват съответно в променливите n, m и k (функция main).
3. От входния файл се прочитат данните за дърветата в горския участък и се записват в по-горе описаните масиви y[ ], x [ ], c[ ] и l[ ] (функция main).
4. Образуват се всички възможни правоъгълници, които могат да се поберат в пределите на правоъгълната мрежа, след което всеки от тях се премества успоредно на линиите в мрежата до всички възможни положения, които може да заеме и които ще наричаме възможни огради (функция process).
5. За избраната в момента една измежду възможните огради с помощта на функцията process се извършва следното:
5.1. В променливата w се записва обиколката на разглежданата възможна ограда.
5.2. В едномерния масив in[ ] се записват номерата на дърветата, който попадат в оградата, в промеливата kin – броят им, а в променливите sumcin и sumlin се пресмятат съответно сумарната цена на тези дървета и сумарната дължина ограда, която може да се направи от тях.
5.3. В едномерния масив out[ ] се записват номерата на дърветата, който остават извън оградата, в промеливата kout – броят им, а в променливите sumcout и sumlout се пресмятат съответно сумарната цена на тези дървета и сумарната дължина ограда, която може да се направи от тях.
5.4. Ако w<=sumlout, то се преминава към 5.5; в противен случай към 5.7.
5.5. Проверява дали sumcout е по-малка от намерената до момента sumc или пък са равни, но kout е по-малко от намереното до момента numc. Ако е така, то е намерено по-добро решение от предишното и данните за него се записват като нови стойности на променливите sumc, numc, tr[ ].
5.6. Преминава се към 5.10.
5.7. За поредната стойност на променливата deficit от (w−sumlout) до sumlin се проверява дали съществуват дървета от вътрешността на оградата, такива че сумарната дължина ограда, която може да се направи от тях (накратко: сумарна оградна дължина), да е равна на deficit, и ако е така, то се преминава към 5.8; в противен случай – към 5.9.
5.8. Подбират се такива дървета със сумарна оградна дължина deficit, че сумарната им цена да бъде възможно най-малка. Последното се прави от функциите knapsack, calculate и checkall, реализиращи разновидност на задачата за раницата, при която се използва таблица и се търси не максималната, а минималната сумарна цена. Проверява се дали ако се отрежат така подбраните дървета заедно с останалите извън оградата дървета, то ще се получи по-добро (в съответствие с условието на задачата) от намереното до момента решение. Ако е така, то данните за въпросното по-добро решение се записват като нови стойности на sumc, numc, tr[ ].
5.9. Ако променливата deficit не превишава sumlin, то отново се изпълнява 5.7; в противен случай – 5.10.
5.10. Ако все още не са изчерпани всички възможните огради, то се преминава към следващата и за нея отново се изпълнява 5; в противен случай се преминава към 6.
6. На първия ред на изходния файл OGRADA.OUT се извеждат стойностите на променливите sumc и numc, разделени с един интервал, а на всеки от следващите редове се извежда по един елемент на масива tr[ ]. 
7. Затварят се файловете OGRADA.INP и OGRADA.OUT, след което се преустановява работата на програмата.

2.12.2001 г.                                                                                             гр. Грамада