Please enable JavaScript.

Coggle requires JavaScript to display documents.

Dynamic Programming - Coggle Diagram

- - - - Neste problema, há uma fila de n moedas com valores positivos c1, c2,...,cn, não necessariamente distintos. O objetivo é pegar a quantidade máxima de dinheiro sujeita à restrição de que nenhuma duas moedas adjacentes na fila inicial podem ser escolhidas.
    - - Dá para dividir o problema de achar o F(n) de uma moeda em dois subproblemas onde, um é F(n - 1) onde a última moeda não está inclusa mas sim o seu anterior, e o d Cn + F(n - 2) onde adicionamos o valor da moeda n ao F da antepenúltima moeda. A solução será o subproblema que tiver o maior valor comparado ao outro
  - - - Neste problema, o objetivo é dar troco para uma quantia n utilizando o menor número possível de moedas de denominações d1 < d2 < ... < dm
    - - Seja F(n) o número mínimo de moedas cujos valores somam n e definindo F(0) = 0, primeiro definimos um conjunto de moedas de denominações que varia de 1 até m, ao fazer isso podemos dizer que, j = {1, 2, 3, ..., m}, F(n) = 1 + min(F(n - D[j]))
        
        Ao fazer isso é tirado do valor n uma moeda de denominação obtendo o valor k ao fazer F(k) obtemos o número necessário de moedas de denominação necessárias para chegar em k ao somar mais 1 adicionamos a última moeda necessária para chegar ao valor n, obter o mínimo desses valores apenas significa encontrar k onde o F(k) é menor que os outros
  - - - Neste problema, várias moedas estão distribuídas em células de um tabuleiro n × m, e um robô, localizado na célula superior esquerda do tabuleiro, precisa coletar o máximo possível de moedas e levá-las para a célula inferior direita. Não pode existir mais de uma moeda por célula e o robô só pode se mover ou para a direita ou para baixo
      - Solução
        
        Considerando F(i, j) o número máximo de moedas que se pode levar para a célula na linha i e coluna j, podemos dividir o problema em dois sendo eles F(i - 1, j) e F(i, j - 1) que são o número máximo de moedas que se pode levar para às células adjacentes da esquerda e de cima respectivamente
        
        Ao escolher o número máximo entre esses dois subproblemas descobrimos qual o número de moedas o robô pode carregar antes de chegar na célula atual, se a célula atual tiver uma moeda somamos mais 1 caso contrário o resultado é o número escolhido
- - - - O problema envolve selecionar um subconjunto de itens, de um conjunto onde cada item possui um valor e um peso não negativo, de modo a maximizar o valor total, respeitando a capacidade de uma mochila.
    - - considerando que F(i, j) é o valor máximo para os primeiros i itens e sendo j a capacidade restante da mochila, é possível dividir o problema em dois, um em que não é adicionado o item ou seja F(i - 1, j) e o que ele é adicionado Vi + F(i - 1, j - Wi)
        
        Caso j - Wi < 0 então a solução é F(i - 1, j), caso contrário, a solução será max(F(i - 1, j), Vi + F(i - 1, j - Wi)), ou seja, a solução consiste em decidir se é melhor adicionar o i-ésimo item ou não
  - - - Para isso servem as Memory Functions que é uma técnica para manter a capacidade de resolver subproblemas uma única vez, mas, resolvendo apenas aqueles que são necessários para chegar a resolução do problema original
- - - - Esses algoritmos de aproximação vão usar um conjunto de heurísticas, uma regra extraída a partir da experiência e não provada matematicamente, que partirão para uma solução aproximada do problema
        
        A solução virá com uma margem de erro que é chamada de ratio onde r(Sa) = f(S*)/f(Sa) onde S* é a solução real, que por muitas vezes não sabemos qual é
        
        Define-se um algoritmo de aproximação c, onde c >= 1, se r(Sa) <= c
        
        Quanto mais próximo de r(Sa) = f(Sa)/f(S*) estiver de 1, mais próxima está a solução computada da solução real