ПРОБЛЕМ С ПРОДАЖБАТА НА ВИНО

Днес ще разгледаме един класически проблем с интервю. Този проблем е задаван в много интервюта за програмиране и се надявам да ви хареса!

Нека да започнем.

Постановка на задача:
Дадени са n вина в ред, като цели числа означават цената на всяко вино съответно. Всяка година можете да продадете първото или последното вино в редицата. Нека първоначалните печалби от вината са P1, P2, P3…Pn. През Y-тата година печалбата от i-тото вино ще бъде Y*P[i]. Целта е да се изчисли максималната печалба, която може да бъде спечелена от продажбата на всички вина.

Да предположим, че масивът вино обозначава първоначалната цена на всяко вино през първата година.

вино [] = [2, 4, 6, 2, 5]

Първоначалната мисъл би била да станете алчни, тоест да проверите двата края и да продавате по-евтиното вино всеки път. Ако го направим алчно,

цена = 2*1 = 2, оставащи вина = [ 4, 6, 2, 5 ], печалба = 2
цена = 4*2 = 8, оставащи вина = [ 6, 2, 5 ], печалба = 10
цена = 5*3 = 15, оставащи вина = [ 6, 2 ], печалба = 25
цена = 2*4 = 8, оставащи вина = [ 6 ], печалба = 33
цена = 6*5 = 30, оставащи вина = [ ], печалба = 63

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

За горното решение действителната оптимална печалба е 64. Нека покажа как:

вино [] = [2, 4, 6, 2, 5]

цена = 2*1 = 2, оставащи вина = [ 4, 6, 2, 5 ], печалба = 2
цена = 5*2 = 10, оставащи вина = [ 4, 6, 2 ], печалба = 12
цена = 2*3 = 6, оставащи вина = [ 4, 6], печалба = 18
цена = 4*4 = 16, оставащи вина = [ 6 ], печалба = 34
цена = 6*5 = 30, оставащи вина = [ ], печалба = 64

И така, тук можем да видим, че във втората стъпка първо се продава вино с цена 5 вместо вино с цена 4. Правейки това, гарантираме, че вино с много евтина цена, която е „2“, се продава в третата година, които иначе биха били продадени през четвъртата година. Следователно, увеличаване на общата печалба.

За да постигна тази цел програмно, първият подход, който ми идва на ум, е да използвам рекурсия. Във всяка стъпка на рекурсия имаме два избора, или да изберете първото вино, или да изберете последното вино.

Да предположим, че инициализираме началната точка като 0 и крайната точка като wine.length-1. Следователно, начало = 0 и край = 4.
Сега ще прегледаме целия винен масив и ще проверим за всяка възможност и ще върнем най-доброто възможно решение.

Нека да разгледаме рекурсивното дърво.

Тук, на всяко ниво, имаме два избора, или да изберем първото вино, или последното вино.

Да предположим, че първо избираме wine[0], след това печалбата = level*wine[0]. Тук всяко ниво представлява годината на продажба на виното.

След като изберем wine[0], ни остава wine[1..4]. Отново имаме два избора, или изберете вино[1] или изберете вино[4]. И същата рекурсия ще се случи за останалите бутилки вино. Във всяка рекурсия ще изберем поддървото, което ще ни даде максимална печалба.
Нека да разгледаме кода, тук leftProfit означава печалба, получена чрез избиране на най-лявото вино, а rightProfit означава печалба, получена чрез избиране на най-дясното вино.

int maxProfit(start, end, year)
{
   if(start==end) return wine[start]*year; //base condition
   leftProfit = wine[start]*year + maxProfit(start+1, end, year+1, wine);
   rightProfit = wine[end]*year + maxProfit(start, end-1, year+1, wine);
return max(leftProfit, rightProfit);
}

И така, имаме общо 2^(n-1) избора. Следователно времева сложност - O(2ⁿ).

Подход за динамично програмиране

Както можем да видим в дървото на рекурсията, има много припокриващи се подпроблеми. Можем да намалим времевата сложност чрез техника за запомняне. Да видим как.

Ще използваме динамично програмиране, за да разрешим този проблем. Създайте 2D масив. Този масив ще съхранява максималната печалба от продажбата на вината. Размерът му ще бъде (вино.дължина*вино.дължина).

int wineProfit[вино.дължина][вино.дължина]; //задайте масива с начални стойности нула, това означава, че печалбата все още не е изчислена.

wineProfit[0][4] = максимална печалба от продажбата на вината от индекс 0 до 4. напр. [2, 4, 6, 2, 5]
wineProfit[1][3] = максимална печалба от продажбата на вината от индекс 1 до 3. напр. [4, 6, 2]
и така нататък.

int maxProfit(start, end, year)
{
    if (start > end)
        return 0;
    else if (wineProfit[start][end] != 0)
        return wineProfit[start][end];
    else if (start <= end){
leftProfit = wine[start] * year + maxprofit(start + 1, end, year + 1);
rightProfit = wine[end] * year + maxprofit(start, end - 1, year + 1);
wineProfit[start][end] = max(leftProfit, rightProfit); //this step is memoization
return wineProfit[start][end];
    }
    else
        return 0;
}

При подхода на DP, когато изчисляваме печалбата, я запазваме в масива, така че ако печалбата трябва да се изчисли отново следващия път, да можем да я използваме повторно и да спестим време и място.

Чрез мемоизация времевата сложност намалява до O(N²).

Надявам се, че този блог ви е харесал. Продължавай да кодираш! :)