Solução Informática Avançado – Semana 49

Solução de Lawrence Melo

Vamos usar a seguinte ideia de programação dinâmica com bitmask, $$dp[2^{n}][n]$$, onde $$dp[mask][i]$$ indica o maior caminho da cidade $$i$$ para a cidade $$n – 1$$ já tendo visitado as cidades salvas na bitmask. Assim, teremos que:

$$dp[mask][i]$$ = $$\begin{cases} 0 & , \mbox{se i = n – 1} \\ \max\limits_{0 \leq v \leq n – 1} \big( dp[mask | 2^{v}][v] + C[i][v] \big) & , \mbox{caso contrario}\end{cases}$$

Checamos sempre se o bit $$v$$ está ligado ou se existe uma rota entre $$i$$ e $$v$$. A complexidade final é, então, $$\mathcal{O}(2^{n} \cdot n^{2})$$.

Código para melhor entendimento:

https://gist.github.com/lawrencefmm/4f1103557fa05216881556de7aee3126