Sobre Programacao Dinamica Existe uma perspective um pouco diferente sobre programacao dinamica (DP) que talvez ajude alguns de voces, em alguns problemas (para os interessados isso 'e a perspectiva de Markov Decision Processes (deterministicos)). Para quem isso mais confundir do que ajudar, pode desconsiderar. Podemos pensar em um problema/modelagem de programacao dinamica como tendo 2 componentes: 1) Decisao: Em cada estado (veja abaixo) temos que decidir alguma coisa. Por exemplo, no problema da mochila, decidimos incluir ou nao o item i (quando em estado (i,w)). No problema de escalonamento de intervalos, decidimos tambem incluir ou nao o intervalo i (quando no estado i). No problema de alinhamento de cadeias, decidimos como casar um ou mais dos elementos xi e yj (quando em estado (i,j)). No problema da consultoria movel (exercicio dos slides), decidimos basear o negocio no Rio ou em SP no proximo instante. O problema da maior subsequencia crescente nao acho tao natural interpretar dessa maneira.... 2) Estado: Sempre que tomamos uma decisao, movemos de um estado para outro (um estado 'e exatamente o que chamamos de subproblema); em cada decisao/movimento, em geral "pagamos"/"recebemos" um valor. Uma coisa importante dos estados 'e que temos que poder saber quais decisoes/acoes podemos tomar em um momento *somente baseado no estado atual*; em particular, os estados tem que conter uma certa quantidade de informacao. Vamos tentar entender/definir a nocao de estado para o problema da mochila, baseado na decisao acima de incluir ou nao um item. Suponha que estamos em um estado (o que quer que isso seja) e estamos decidindo para o item i se devemos inclui-lo ou nao. Note que so podemos incluir esse item se: 1) ele nao estiver ja sido incluido; 2) couber na mochila, dadas as decisoes que ja tomamos. Ou seja, o estado tem que conter essas 2 informacoes. Se decidirmos incluir o item i, devemos transicionar para um estado onde o item i nao esta mais disponivel, e o tamanho da mochila perdeu mais wi unidades de tamanho (e nessa transicao ganhamos valor +vi); se decidirmos nao incluir o item i, devemos transicionar para um estado onde o item i nao esta disponivel mas a mochila restante nao se altera. Baseado nisso, a primeira ideia 'e definir como estado os pares (S,w), onde S 'e o conjunto de itens disponiveis e w a mochila disponivel nesse estado. (Um pequeno problema 'e que nao 'e claro sobre qual item i estamos tomando a decisao em um estado.) Mas o grande problema com isso 'e que temos um numero exponencial de estados, pois temos 2^n subconjuntos de itens possiveis; para resolver uma DP, vamos ter que preencher uma tabela com uma entrada para cada estado (como serpre fazemos), entao nesse caso o algoritmo seria pelo menos Omega(2^n), queremos melhor. Uma ideia para reduzir o numero de estados 'e definir um estado so como os pares (i,w), indicando que exatamente os itens 1,2,...,i estao disponiveis, e a mochila disponivel 'e w nesse estado. Agora so temos n*W estados. Quais sao as transicoes? No estado (i,w), para qual item devemos escolher inclui-lo ou nao? Se escolhermos incluir/nao um item j < i (ou seja diferente de i), o proximo estado para o qual vamos transicionar nao pode incluir o j (independente se incluimos ele ou nao), entao o conjunto de itens possiveis seria da forma 1,2,..,j-1,j+1,...,i; mas nao tem estado modelando essa possibilidade. Entao vamos escolher tomar a decisao para o item i. Ai ficou mais facil: Caso desejamos incluir esse item transicionamos para o estado (i-1,w-wi), e caso desejamos nao incluir transicionamos para o estado (i-1,w). Qual dessas 2 opcoes devemos escoher? De novo, seja OPT(ESTADO) o valor maximo que conseguimos quando estamos atualmente no estado ESTADO. Se estamos no estado (i,w) e decidirmos incluir o item i, gamanhos valor vi mais o maximo valor obtido a partir do estado (i-1,w-wi), ou seja vi + OPT(i-1,w-wi); caso decidimos nao incluir, obtemos valor OPT(i-1,w). Devemos escolher a decisao que maximiza o valor total, e com isso temos o maximo valor que podemos obter a partir do nosso estado: OPT(i,w) = max{vi + OPT(i-1,w-wi), OPT(i-1,w)}. Podemos pensar que comecamos esse processo no estado (n,W), ou seja, estamos interessados em OPT(n,W). Com isso modelamos o problema como DP. Para *resolver* esse problema, usamos o processo iterativo de preencher a tabela ou recursivo com memoizacao. Essa mesma ideia pode ser usada em outros problemas; por exemplo, como seriam as acoes/estados para o problema da consultoria movel?