<filename>report/main.tex
\documentclass[a4paper, 12pt]{article}
\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc}
\usepackage{indentfirst}
\usepackage{graphicx}
\usepackage[font=footnotesize,labelfont=bf]{caption} %muda o tamanho das caption e deixa em negrito
\usepackage{cite}
\usepackage{color}   %May be necessary if you want to color links
\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    citecolor=blue,
    filecolor=blue,
    linkcolor=blue,
    urlcolor=blue
}
\usepackage{listings}
\renewcommand{\lstlistingname}{Algoritmo}
% \definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
% \definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
\lstdefinestyle{mystyle}{
    backgroundcolor=\color{backcolour},   
    % commentstyle=\color{codegreen},
    % keywordstyle=\color{magenta},
    numberstyle=\tiny\color{codegray},
    % stringstyle=\color{codepurple},
    basicstyle=\footnotesize,
    breakatwhitespace=false,         
    breaklines=true,                 
    captionpos=b,                    
    keepspaces=true,                 
    numbers=left,                    
    numbersep=5pt,                  
    showspaces=false,                
    showstringspaces=false,
    showtabs=false,                  
    tabsize=2
}
\lstset{style=mystyle}

\begin{document}
\begin{titlepage}
    \begin{center}
		\LARGE{Universidade Federal de Mato Grosso do Sul}\\
		\vspace{5pt}
        \large{Campus Ponta Porã}\\ 
        \large{{\textbf{Análise de Algoritmos I}}}\\ 
        \vspace{15pt}
        \vspace{95pt}
        \textbf{\large{Trabalho Prático II}}\\
        \vspace{15pt}
        \textbf{\LARGE{Problema da Mochila Booleana}}\\
        %\title{{\large{Título}}}
        \vspace{3,5cm}
    \end{center}
    
    \begin{flushleft}
        \begin{tabbing}
            Aluno: <NAME>\\            
            Professor: <NAME>\\
            %Professor co-orientador: \\
    \end{tabbing}
 \end{flushleft}
    \vspace{1cm}
    
    \begin{center}
        \vspace{\fill}
            Maio\\
         2019
            \end{center}
\end{titlepage}

\clearpage
\tableofcontents
\thispagestyle{empty}
\clearpage

% ref
% https://en.wikibooks.org/wiki/LaTeX/Labels_and_Cross-referencing
% tabela
% https://www.tablesgenerator.com/#

\pagenumbering{arabic}
\section*{Resumo}
\addcontentsline{toc}{section}{Resumo}
\label{sec:resumo}
Este trabalho consiste em mostrar os resultados obtidos a partir da execução
do algoritmo da {\it Mochilha Boolena} ou {\it Knapsack 0/1}, em suas versões dinâmicas.

Feito isso, dada as instâncias contento os dados necessários para aplicar os algoritmos, foi comparado o tempo de execução para cada instância 
nas suas versões dinâmicas, {\it Top-Down} e  {\it Bottom-Up}.\\

{\bf Considerar o seguinte ambiente para a obtenção dos resultados:}
\begin{itemize}
    \item Processador: Intel Core™ i5-8250U
    \begin{itemize}
        \item Número de núcleos 4
        \item Número de threads 8
        \item Frequência baseada em processador 1.60 GHz
        \item Frequência turbo max 3.40 GHz
    \end{itemize}
    \item Memória: 8GB RAM
\end{itemize}
Este trabalho foi armazenado num repositório {\it GitHub} para melhor controle do versionamento do programa.\\
\url{https://github.com/danbailo/T2-Analise-Algoritmos-I}
\clearpage

\section{Introdução}\label{sec:introducao}

Supondo que uma mochila com capacidade total de $W$ e $n$ itens distintos, em que cada um dos itens
possui um peso $p_i$ e um valor $v_i$ , tal que $1 \leq i \leq n$. O {\it Problema da Mochila 0/1} consiste em determinar o 
valor máximo que podemos obter colocando um subconjunto de itens na mochila, tal que o somatório
do peso dos itens não ultrapasse a capacidade $W$ da mochila.

Visto que na {\it Programação Dinâmica} os problemas podem ser abordados de duas formas, o {\it Top-Down} e o {\it Bottom-Up}
, devemos saber que entre eles existem vantagens e desvantagens quando comparados um com o outro.\\~\\
{\bf Top-Down}

Simplesmente uma recursão normal com a adição de uma tabela {\it memoization}. \\~\\
{\bf Bottom-Up} 
\begin{itemize}
    \item Prepare uma tabela com o tamanho do número de estados do problema.
    \item Comece a preencher a tabela através de casos triviais.
    \item Preencha a tabela de acordo com a ordem topológica do problema.\\~\\
\end{itemize}
{\bf Vantagens e Desvantagens}
\begin{itemize}
    \item Top-Down
    \begin{itemize}
        \item Transformação natural através da recursão.
        \item Apenas computa um subproblema se ele for necessário.
        \item Mais lento se ocorrerem muitas chamadas a subproblemas devido ao overhead recursivo.
    \end{itemize}
    \item Bottom-Up
    \begin{itemize}
        \item Mais rápido se muitos subproblemas são computados.
        \item Pode ter uma economia de espaço em alguns casos (não precisar criar uma tabela com todos os subproblemas).
        \item Não é tão intuitivo.
        \item Computa todos os subproblemas.
    \end{itemize}
\end{itemize}


\clearpage
\section{Knapsack Top-Down}\label{sec:topdown}
Código do algoritmo {\it Knapsack 0/1 Top-Down} que foi utilizado para obter os resultados onde o mesmo foi escrito
na linguagem de programação {\it Python}.\\
\begin{lstlisting}[language=Python, caption=Top-Down, label=alg:topdown]
def Knapsack(number_items, weight_max, values_items, weight_items):
    if number_items == 0 or weight_max == 0: return 0
    if weight_items[number_items-1] > weight_max: 
        return Knapsack(number_items-1,weight_max,values_items,weight_items)
    if mem[number_items][weight_max] is not False: 
        return mem[number_items][weight_max]    
    temp = max(Knapsack(number_items-1, 
    weight_max-weight_items[number_items-1],values_items, weight_items)+values_items[number_items-1], Knapsack(number_items-1, weight_max, values_items, weight_items))    
    mem[number_items][weight_max] = temp
    return temp
\end{lstlisting}

\subsection{Resultados}

Após aplicar o algoritmo \nameref{alg:topdown} nas instâncias propostas pelo professor, os seguintes resultados
foram obtidos.
\begin{table}[!htb]
    \begin{tabular}{ll}
    \textbf{Tempo total para executar todas instâncias:} & 28.5181 segundos \\
    \textbf{Média de tempo de execução por instância:} & 0.9199 segundos \\
    \textbf{Maior tempo gasto por uma das instâncias:} & 1.8031 segundos \\
    \textbf{Menor tempo gasto por uma das instâncias:} & 0.25080 segundos \\
    \textbf{Instância com maior tempo de execução:} & s025.kp \\
    \textbf{Instância com menor tempo de execução:} & s011.kp
    \end{tabular}
    \caption{Resultados Top-Down para 1 execução}
    \label{tab:topdown_exec}
\end{table}
% \vspace{-15pt}
\begin{table}[!htb]
    \begin{tabular}{ll}
    \textbf{Amplitude:} & 1.5523 segundos \\
    \textbf{Erro:} & 0.1190 segundos \\
    \textbf{Variância:} & 0.4251 segundos \\
    \textbf{Desvio Padrão:} & 0.6520 segundos \\
    \textbf{Desvio Absoluto:} & 0.2629 segundos
    \end{tabular}
    \caption{Estatísticas}
    \label{tab:estatistica_topdown}
\end{table}

\newpage
Nos gráficos representados pelas figuras \ref{fig:scatter_topDown} e \ref{fig:result_topDown}, podemos ver o tempo
que cada instâncias demorou para antingir tal resultado e qual resultado foi obtido, respectivamente. 
Na figura \ref{fig:time_topDown} conseguimos vizualizar o tempo de execução para cada instância.
\begin{figure}[!htb]
    \centering
    \begin{minipage}{0.55\textwidth}
        \centering
        \includegraphics[width=1.1\textwidth]{../img/scatter_topDown.pdf}
        \caption{Tempo/Resultado.}
        \label{fig:scatter_topDown}
    \end{minipage}%
    \begin{minipage}{0.55\textwidth}
        \centering
        \includegraphics[width=1.1\textwidth]{../img/result_topDown.pdf}
        \caption{Resultado/Instância.}
        \label{fig:result_topDown}
    \end{minipage}
\end{figure}

\begin{figure}[!htb]
    \centering
    \includegraphics[width=0.9\textwidth]{../img/time_topDown.pdf}
    \caption{Gráfico do Tempo/Instância.}
    \label{fig:time_topDown}
\end{figure}

\clearpage
\section{Knapsack Bottom-Up}\label{sec:bottomup}
Código do algoritmo {\it Knapsack 0/1 Bottom-Up} que foi utilizado para obter os resultados onde o mesmo foi escrito
na linguagem de programação {\it Python}.\\
\begin{lstlisting}[language=Python, caption=Bottom-Up, label=alg:bottomup]
def Knapsack(number_items, weight_max, values_items, weight_items): 
    K = [[0 for x in range(weight_max + 1)] for x in range(number_items + 1)]
    for i in range(number_items + 1): 
        for w in range(weight_max + 1): 
            if i == 0 or w == 0: K[i][w] = 0
            elif weight_items[i-1] <= w: 
                K[i][w] = max(values_items[i-1]+K[i-1][w-weight_items[i-1]], K[i-1][w]) 
            else: K[i][w] = K[i-1][w] 
    return K[number_items][weight_max]
\end{lstlisting}

\subsection{Resultados}

Após aplicar o algoritmo \nameref{alg:bottomup} nas instâncias propostas pelo professor, os seguintes resultados
foram obtidos.
\begin{table}[!htb]
    \begin{tabular}{ll}
    \textbf{Tempo total para executar todas instâncias:} & 19.5897 segundos \\
    \textbf{Média de tempo de execução por instância:} & 0.6319 segundos \\
    \textbf{Maior tempo gasto por uma das instâncias:} & 1.2442 segundos \\
    \textbf{Menor tempo gasto por uma das instâncias:} & 0.1975 segundos \\
    \textbf{Instância com maior tempo de execução:} & s025.kp \\
    \textbf{Instância com menor tempo de execução:} & s014.kp
    \end{tabular}
    \caption{Resultados Bottom-Up para 1 execução}
    \label{tab:bottomup_exec}
\end{table}

% \vspace{-15pt}

\begin{table}[!htb]
    \begin{tabular}{ll}
    \textbf{Amplitude:} & 1.0466 segundos \\
    \textbf{Erro:} & 0.0763 segundos \\
    \textbf{Variância:} & 0.1750 segundos \\
    \textbf{Desvio Padrão:} & 0.4184 segundos \\
    \textbf{Desvio Absoluto:} & 0.1227 segundos
    \end{tabular}
    \caption{Estatísticas}
    \label{tab:estatistica_bottomup}
\end{table}

\newpage
Nos gráficos representados pelas figuras \ref{fig:scatter_topDown} e \ref{fig:result_topDown}, podemos ver o tempo
que cada instâncias demorou para antingir tal resultado e qual resultado foi obtido, respectivamente. 
Na figura \ref{fig:time_topDown} conseguimos vizualizar o tempo de execução para cada instância.
\begin{figure}[!htb]
    \centering
    \begin{minipage}{0.55\textwidth}
        \centering
        \includegraphics[width=1.1\textwidth]{../img/scatter_bottomUp.pdf}
        \caption{Tempo/Resultado.}
        \label{fig:scatter_bottomUp}
    \end{minipage}%
    \begin{minipage}{0.55\textwidth}
        \centering
        \includegraphics[width=1.1\textwidth]{../img/result_bottomUp.pdf}
        \caption{Resultado/Instância.}
        \label{fig:result_bottomUp}
    \end{minipage}
\end{figure}

\begin{figure}[!htb]
    \centering
    \includegraphics[width=0.9\textwidth]{../img/time_bottomUp.pdf}
    \caption{Gráfico do Tempo/Instância.}
    \label{fig:time_bottomUp}
\end{figure}

\clearpage
\section{Análise dos Resultados}
Como podemos ver abaixo, na figura \ref{fig:result_two}, que é responsável por mostrar os resultados atingidos
para cada instância, os gráficos estão sobrepostos e isso se deve pelo fato de que, independente dos algoritmos
serem escritos e abordarem ideias diferentes, o objetivo final é o mesmo.
\begin{figure}[!h]
    \centering
    \includegraphics[width=0.6\textwidth]{../img/result_two.pdf}
    \caption{Gráfico comparativo dos resultados.}
    \label{fig:result_two}
\end{figure}

Abaixo, podemos ver que o tempo necessário para atingir os mesmos resultados são bem maiores quando
comparamos o \nameref{sec:topdown} ao \nameref{sec:bottomup}, computacionalmente falando. Porém, era de
se esperar um resultado como esse, como vimos na página \pageref{sec:introducao} as características de cada um.

\begin{figure}[!htb]
    \centering
    \begin{minipage}{0.55\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{../img/scatter_two.pdf}
        \caption{\footnotesize{Gráfico do Tempo/Resultado}}
        \label{fig:scatter_two} 
    \end{minipage}%
    \begin{minipage}{0.6\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{../img/time_two.pdf}
        \caption{\footnotesize{Gráfico do Tempo/Instância}}
        \label{fig:time_two}
    \end{minipage}
\end{figure}
\newpage
\subsection{Minimizando Resultados}
A fim de comprovar o comportamento dos gráficos, decidi executar {\bf 100 vezes} as instâncias com o objetivo de minimizar
a variação do tempo de execução de cada instância.

Para cada instância é armazenado seu tempo de execução individual, logo, foi necessário a cada execução
armazenar e somar o tempo de cada instância para obter o tempo gasto para esse algoritmo para uma única execução. Feito isso, bastou
repetir o mesmo processo para todas iterações. Assim, obtive o tempo total de execução para os dois algoritmos. 
O tempo médio é em relação ao tempo que uma única instância gastou em 100 execuções.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Top-Down}
\begin{table}[!htb]
    \begin{tabular}{ll}
        {\bf Tempo total de execução}: 39 minutos\\
        {\bf Tempo médio gasto por cada instância no total}: 1 minuto e 25 seg
    \end{tabular}
    \caption{Tempo total}
    \label{tab:total_topdown}
\end{table}

Após coletar os dados de todas as execuções, foi calculado a média total para cada item e obtido um resultado 
mais exprimido a fim de minimizar a variação.
\begin{table}[!htb]
    \begin{tabular}{ll}
        {\bf Tempo de execução}: 23.4481 segundos\\
        {\bf Média de execução por instância}: 0.7563 segundos\\
        {\bf Maior tempo gasto por uma das instâncias}: 1.3748 segundos\\
        {\bf Menor tempo gasto por uma das instâncias}: 0.2420 segundos \\
        {\bf Instância com maior tempo de execução}: s027.kp\\
        {\bf Instância com menor tempo de execução}: s014.kp
    \end{tabular}
    \caption{Resultados a partir de 100 execuções}
    \label{tab:result_tot_topdown}
\end{table}

% \vspace{-15pt}

\begin{table}[!htb]
    \begin{tabular}{ll}
        {\bf Amplitude}: 1.1327 segundos\\
        {\bf Erro}: 0.0907 segundos\\
        {\bf Variância}: 0.2472 segundos\\
        {\bf Desvio Padrão}: 0.4972 segundos\\
        {\bf Desvio Absoluto}: 0.1421 segundos
    \end{tabular}
    \caption{Estatísticas}
    \label{tab:estatistica_tot_topdown}
\end{table}

\subsubsection{Ganhos}

Ao compararmos os resultados das tabelas \ref{tab:topdown_exec} e \ref{tab:estatistica_topdown} com as 
tabelas \ref{tab:result_tot_topdown} e \ref{tab:estatistica_tot_topdown}, podemos ver qual é a diferença entre 
entre os seguintes resultados obtidos:
\begin{table}[!htb]
    \begin{tabular}{ll}
        {\bf p/ Tempo de execução}: 5.07 segundos\\
        {\bf p/ Média de execução por instância}: 0.1636 segundos\\
        {\bf p/ Maior tempo gasto por uma das instâncias}: 0.4282 segundos\\
        {\bf p/ Menor tempo gasto por uma das instâncias}: 0.0088 segundos \\
    \end{tabular}
    \caption{Diferença de 1 execução para 100 execuções}
    \label{tab:diff_topdown}
\end{table}

% \vspace{-15pt}

\begin{table}[!htb]
    \begin{tabular}{ll}
        {\bf p/ Amplitude}: 0.4196 segundos\\
        {\bf p/ Erro}: 0.0282 segundos\\
        {\bf p/ Variância}: 0.1778 segundos\\
        {\bf p/ Desvio Padrão}: 0.1548 segundos\\
        {\bf p/ Desvio Absoluto}: 0.1208 segundos
    \end{tabular}
    \caption{Estatísticas}
    \label{tab:diff_estatistica_topdown}
\end{table}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\hrulefill

\subsection{Bottom-Up}
\begin{table}[!htb]
    \begin{tabular}{ll}
        {\bf Tempo total de execução}: 29 minutos\\
        {\bf Tempo médio gasto por cada instância no total}: 55.9276 segundos
    \end{tabular}
    \caption{Tempo total}
    \label{tab:total_bottomup}
\end{table}
% aqui falar do porque de fazer a media...\\
Após coletar os dados de todas as execuções, foi calculado a média total para cada item e obtido um resultado 
mais exprimido a fim de minimizar a variação.
\begin{table}[!htb]
    \begin{tabular}{ll}
        {\bf Tempo de execução}: 17.3945 segundos\\
        {\bf Média de execução por instância}: 0.5611 segundos\\
        {\bf Maior tempo gasto por uma das instâncias}: 0.9881 segundos\\
        {\bf Menor tempo gasto por uma das instâncias}: 0.1927 segundos \\
        {\bf Instância com maior tempo de execução}: s027.kp\\
        {\bf Instância com menor tempo de execução}: s014.kp
    \end{tabular}
    \caption{Resultados a partir de 100 execuções}
    \label{tab:result_tot_bottomup}
\end{table}

% \vspace{-15pt}

\begin{table}[!htb]
    \begin{tabular}{ll}
        {\bf Amplitude}: 0.7954 segundos\\
        {\bf Erro}: 0.0638 segundos\\
        {\bf Variância}: 0.1221 segundos\\
        {\bf Desvio Padrão}: 0.3495 segundos\\
        {\bf Desvio Absoluto}: 0.1244 segundos
    \end{tabular}
    \caption{Estatísticas}
    \label{tab:estatistica_tot_bottomup}
\end{table}

\subsubsection{Ganhos}

Ao compararmos os resultados das tabelas \ref{tab:bottomup_exec} e \ref{tab:estatistica_bottomup} com as 
tabelas \ref{tab:result_tot_bottomup} e \ref{tab:estatistica_tot_bottomup}, podemos ver qual é a diferença entre 
entre os seguintes resultados obtidos:
\begin{table}[!htb]
    \begin{tabular}{ll}
        {\bf p/ Tempo de execução}: 2.1952 segundos\\
        {\bf p/ Média de execução por instância}: 0.0707 segundos\\
        {\bf p/ Maior tempo gasto por uma das instâncias}: 0.2561 segundos\\
        {\bf p/ Menor tempo gasto por uma das instâncias}: 0.0047 segundos \\
    \end{tabular}
    \caption{Diferença de 1 execução para 100 execuções}
    \label{tab:diff_bottomup}
\end{table}

% \vspace{-15pt}

\begin{table}[!htb]
    \begin{tabular}{ll}
        {\bf p/ Amplitude}: 0.2512 segundos\\
        {\bf p/ Erro}: 0.0125 segundos\\
        {\bf p/ Variância}: 0.0528 segundos\\
        {\bf p/ Desvio Padrão}: 0.0689 segundos\\
        {\bf p/ Desvio Absoluto}: -0.0016 segundos
    \end{tabular}
    \caption{Estatísticas}
    \label{tab:diff_estatistica_bottomup}
\end{table}

\noindent
Como podemos ver, o objetivo de minimizar a variação foi atingido. Visto que, para o {\it Top-Down} teve um
ganho de 5.07 segundos e para o {\it Bottom-Up} 2.1952 segundos, tempo que, computacionalmente falando, já é muito alto!

Em relação aos dados estatísticos, todos foram minimizados também, isso mostra que, quanto menor o erro, variação e 
o desvio, mais próximo do exato é o resultado final.

\newpage

\section{Resultados Obtidos}
A figura abaixo representa o gráfico dos resultados obtidos após realizar a média de 100 execuções das instâncias,
como foi visto nas tabelas \ref{tab:result_tot_topdown} e \ref{tab:result_tot_bottomup}.

\begin{figure}[!htb]
    \centering
    \includegraphics[width=0.7\textwidth]{../img/avg_scatter.pdf}
    \caption{Gráfico do Tempo/Resultado}
    \label{fig:avg_scatter}
\end{figure}
\begin{figure}[!htb]
    \centering
    \includegraphics[width=0.8\textwidth]{../img/avg_result.pdf}
    \caption{Gráfico do Tempo/Instância}
    \label{fig:avg_result}
\end{figure}
\clearpage

\subsection{Resultados Finais}
Com isso, podemos concluir que, o objetivo de minimizar a variação do tempo de cada execução foi atingida.

Nos gráficos abaixo, temos ilustrado o tempo que demandou cada resultado, sendo que, as legendas que possuem
{\it ''AVG''} no nome, significa que são os gŕaficos após realizar a média entre as 100 execuções.
Logo, é uma mesclagem das figuras \ref{fig:time_two} e \ref{fig:avg_result}.

Portanto, estas figuras representam a união de todos resultados mostrados até agora.

\begin{figure}[!htb]
    \centering
    \begin{minipage}{0.55\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{../img/mixed_scatter.pdf}
        \caption{Resultados - Mesclado}
        \label{fig:mixed_result}   
    \end{minipage}%
    \begin{minipage}{0.6\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{../img/mixed_result.pdf}
        \caption{Resultados - Mesclado}
        \label{fig:mixed_scatter}
    \end{minipage}
\end{figure}
\end{document}