Solução Informática Avançado – Semana 50 – Problema 1

Solução de Lúcio Cardoso

Este problema é o clássico Problema da Mochila (ou Knapsack), porém com algumas restrições adicionais que nos impossibilitam de resolver-lô da maneira tradicional.

Note que, como cada $$v_i < 10^3$$ e $$N < 100$$, a resposta máxima será no máximo $$10^5$$. Faremos então a seguinte Programação Dinâmica: Seja $$dp[i][j]$$ a menor soma de pesos possível para conseguir um valor total $$j$$, considerando os livros desde 1 até $$i$$. Assim,

$$dp[i][j]$$ = $$\begin{cases} 0 & , \mbox{se j = 0 ou i = 0} \\ \min \big( dp[i – 1][j] , dp[i – 1][j – v_i] + w_i \big) & , \mbox{caso contrario (podemos usar ou nao o i-esimo livro)}\end{cases}$$

Logo, a resposta para o problema é o maior valor possível $$V$$ tal que $$dp[N][V] <= W$$. Ou seja, queremos conseguir o valor $$V$$ sem ultrapassar a capacidade da mochila.

A complexidade final será $$\mathcal{O}(N \cdot V)$$, onde $$V$$ é a maior soma de $$v_i$$ possível. Confira o código para melhor entendimento:

https://gist.github.com/luciocf/03c00c589686dae178379b7e0e901ddb