\documentclass[12pt]{article} 
\input{ejoi_structure_analysis.tex}

\usepackage[bulgarian]{babel}
\usepackage{emoji}

\begin{document}

\renewcommand{\problemName}{Задача Раница}

\section{Анализ на задача knapsack}
\begin{center}
	Решения: Димитър Шапатов; Условие, анализ: Кирил Зашев
\end{center}

Ако по време на състезанието сте се чудили дали формулата е някакъв трол, например че не се иска да намерите най-оптималното решение за 100 точки -- всъщност не е трол, и това може би е трол часта в тази задача \emoji{smiley}).

Ето три възможни подхода за решение на тази задача:
\subsection{Hill Climb}
Това е най-естествения подход за output-only задача, а следното е само една възможна идея.
Първоначално взимаме някакво случайно множество от предмети. На всяка една итерация на hill climb можем да вземем един случаен предмет от заетите предмети (тези, които в момента участват в отговора) и да го махнем. След това може да слагаме случайни предмети от свободните елементи (тези, които не участват в отговора) в множеството, докато теглото е $\leq W$.

Връщаме предишното състояние на предметите, ако то е по-оптимално от новото. Има една особеност при имплементацията - как ще поддъжаме динамично множествата от заетите и свободните предмети, така че да можем да достъпим бързо и случайни елементи в тях? Най-вероятно няма структура, която да поддържа тези операции константно, но можем да направим това за $O(\log N)$.

В авторските решения е използван \texttt{ordered\_set}, като се възползваме от това, че може да намира $k$-тия по големина елемент за $O(\log N)$ (тоест идеята е да избираме случайно число за $k$). Едно такова решение се оказва, че не работи добре спрямо формулата (взима само около 10 точки, дори и да се пусне за много време). Възможно е и да се оптимизира начина, по който избираме кой предмет да махнем, или пък да махаме повече от един предмет, но такива решения най-вероятно пак няма да успеят да вземат хубави точки.

\subsection{Fractional Knapsack}
За тези, които не са чували за тази раница -- идеята е да сортираме предметите по съотношението цена/тегло и да ги взимаме последователно, докато теглото не стане по-голямо от W. Тази стратегия се чупи, ако трябва да намерим точния най-добър отговор, но работи сравнително добре, когато трябва да се приближим към най-добрия отговор.
За жалост, отново заради гадната формула, това решение дава едва около 10 точки.

\subsection{Fractional Knapsack + Hill Climb}
Идеята е вместо да започнем hill climb от случайно множество, почваме от множеството, което намери fractional knapsack. Това решение вече има по-голям шанс за успех, но гадното в тази задача (и може би заради това е хубаво, че е в по-лесния ден) е, че hill climb трябва да се пусне за много време, за да направи много точки -- ако е написано хубаво, може да стигне до около 80 точки с около 2 часа време на изпълнение.

Решението knapsack\_combined.zip изкарва 100 точки на задачата, а то е комбинация от леки вариации на решението по-горе. Чист архив на решението по-горе има в knapsack\_best.zip за 76.86т.

\end{document}
