Задачата изисква цената на отсечените дървета да е минимална. Условието прилича отчасти на задачата за раницата, но факта, че трябва да се съобразим и с разположението на дърветата ме накара да смятам, че стандартния оптимизационен подход е неприложим за тази задача.

Рекурсивната процедура Fn, която лежи в основата на решението е съвсем проста. Чрез нея аз всъщност решавам обратната задача на търсената - опитвам се да намеря, кои дървета трябва да останат не отсечени, така че цената им (евентуално и броя им) да бъде максимален. Рекурсивната процедура съставя всички подмножества на даденото множество от дървета - примерно при 3 дървета рекурсията ще състави следните множества: [1], [1,2], [1,2,3], [1,3] [2],[2,3],[3]. (Празното м-во не е решение, според условието на задачата).

При всяко викане на рекурсията предавам, като параметри текущото дърво, площта на дърветата, които не са отсечени, до момента, (т.е най-големия и най-малкия X измежду x-овете на всички не отсечени, дървета и най-големия и най-малкия Y измежду y-ците на не отсечените дървета). Също предавам, като параметър количеството дървен материал от отсечените до момента дървета, цената и броя на не отсечените до момента дървета.

Рекурсивната процедура започва с актуализиране на обема отсечен материал, като от общия материал се вади материала за текущото дърво. След това актуализирам максималните x-ове и y-ци, в зависимост от текущото дърво (ако е нужно изобщо). След това изчислявам дължината на нужната ограда, по формулата (максимален X - минимален X+1)*2+(максимален Y - минимален Y+1)*2. Намирам разликата между наличния материал и нужната дължина на оградата. Ако тази разлика е отрицателна, очевидно това няма как да е решение и връщам рекурсията стъпка назад.

Ако разликата не е отрицателна прибавям текущото дърво към не отсечените (използвайки масив с булеви променливи). Изчислявам новата текуща цена и текущ брой. Ако те са по-големи от максималните, то приемам тях за максимални. След това продължавам да търся решението по рекурсивен начин за дърветата с номера, по голям от номера на текущото дърво. При рекурсивната стъпка назад махам текущото дърво от множеството на не отсечените

Очевидно тази процедура решава задачата, но за голям брой дървета, това решение работи твърде бавно. Нужни са оптимизации. Най-простата оптимизация, за която се сетих бе предварително да сортирам дърветата по цените им в намаляващ ред, а тези с еднакви цени - по дървения им материал в нарастващ ред. По този начин програмата вървеше неколкократно по-бързо, но разбира се недостатъчно. Сложността на рекурсията е експоненциална и за да се получи решение в смислен период от време е нужно част от клоните на рекурсията да се отрежат и колкото по-близо до основата, толкова по-добре.

Затова направих следната оптимизация: в два масива сортирах цените и дървения материал на всички дървета. След това с тяхна помощ съставих двумерен масив за цените, като за всяко дърво в него записах максималната възможна цена, която може да се постигне, ако не се отсекат следващите 1,2,3 и т.н. дървета. (примерно: за дърво с номер 22: първата клетка на реда за това дърво съдържа най-високата цена на дърво в редицата: 23,24,...N. N е броя на дърветата. Втората клетка съдържа сумата на двете най-скъпи дървета в тази редица, третата съдържа сумата на 3те най-скъпи и т.н.) Съставих същия двумерен масив и за дървения материал, но там се започва с дърветата с най-малко дървен материал, т.е масива за всяко дърво расте обратно на този за цените.

Идеята на всичко това е преди всяко викане на рекурсията за дадено дърво да мога да направя някаква груба оценка за това колко максимално може да се вдигне текущата цена, ако не отсека следващите след него 1,2,3 и т.н. дървета, преди намалелият поради не отсичането им дървен материал да стане по-голям от текущата дължина на оградата. Т.е първо гледам колко максимално дървета след текущото дърво мога да не отсека и съответно колко е максималната цена, която мога да получа от този брой дървета. Ако тази максимална цена събрана с текущата е по-малка от постигната досега изобщо максимална цена, то този клон на рекурсията е безперспективен. Това, както се досещате е много груба оценка, но тя наистина драстично намалява броя на влизанията в рекурсията. Опитах се да подобря тази оценка, като вземам в предвид и местоположението на следващите дървета по подобен начин с 4 двумерни масива за максималните и минимални x-ове и y-ци, но това не доведе до желания резултат. Влизанията в рекурсията намаляха около десетина пъти, но сложността на рекурсивната процедура стана твърде голяма. (т.е влизанията в рекурсията по времето за изпълнение на едно влизане даваше по-голямо число). Така че в крайния вариант на задачата изоставих това и останаха само окастрянията на рекурсията съобразно цените на дърветата и количеството дървен материал за всяко дърво.

Накрая забелязах, че това колко дървета могат да не се отсекат след текущото дърво зависи единствено от текущия излишен дървен материал, който представлява цяло число. Затова използвах своеобразен вид динамично оптимиране, като записвах в таблица максимално възможните за постигане цени за всяко дърво и за всеки излишък от дървен материал, така че ако рекурсията попадне в същата ситуация просто гледа в таблицата дали тази стойност вече не сметната и ако да - я използва наготово. Тази последна оптимизация е ужасно неефективна откъм памет, но все пак пести някоя милисекунда.

Това е :-))