Please enable JavaScript.

Coggle requires JavaScript to display documents.

MM12 - Coggle Diagram

- - - - Formulação DP
        
        Condições iniciais
        
        F(1) = coin[0]
        
        F(0) = 0
        
        Recorrência
        
        F(i) = max(coin[i-1] + F(i-2), F(i-1))
        
        Definir F(i) = valor máximo possível das primeiras i moedas.
      - Exemplo
        
        Solução ótima: 5 + 10 + 2 = 17
        
        Moedas: [5, 1, 2, 10, 6, 2]
      - Dada uma sequência de moedas em linha, escolher um subconjunto sem pegar duas consecutivas, de forma a maximizar o valor total.
  - - - Formulação DP
        
        Condição inicial
        
        C(0) = 0
        
        Recorrencia
        
        C(x) = min(C(x-c) + 1) para todo c ∈ moedas e c ≤ x
        
        Definir C(x) = número mínimo de moedas para valor x.
      - Exemplo
        
        Solução ótima: 2 moedas (3 + 3)
        
        Valor: 6
        
        Moedas: [1, 3, 4]
      - Dado um conjunto de moedas e um valor-alvo, determinar o número mínimo de moedas necessárias para formar esse valor.
  - - - Formulação DP
        
        Condição inicial:
        
        C(0,0) = coin(0,0)
        
        Recorrência:
        
        C(i,j) = max(C(i-1,j), C(i,j-1)) + coin(i,j)
        
        Definir C(i,j) = moedas máximas coletadas até a posição (i,j).
      - Exemplo
        
        Melhor caminho: máximo número de moedas
        
        Grid
        
        1 5 3 1
        
        2 0 0 4
        
        0 3 1 1
      - Dada uma matriz com moedas em algumas posições, encontrar o caminho da origem ao destino que colete o máximo de moedas.
- - - - Dados n itens com peso e valor, selecionar um subconjunto para maximizar o valor total sem ultrapassar a capacidade máxima da mochila.
    - - 0/1 Knapsack: leva 100% de item levado ou não o leva.
      - Fractional Knapsack: item pode ser fracionado.
    - - Itens: [(peso: 2, valor: 3), (peso: 3, valor: 4), (peso: 4, valor: 5)]
      - Capacidade: 5
    - - Definir K(i, w) = valor máximo com os primeiros i itens e capacidade w.
      - Recorrência
        
        Se peso[i-1] ≤ w:
        
        K(i, w) = max(valor[i-1] + K(i-1, w-peso[i-1]), K(i-1, w))
        
        Se não:
        
        K(i, w) = K(i-1, w)
      - Condição inicial
        
        K(0, w) = 0 para todo w
  - - - Sobreposição de subproblemas.
      - Existência de uma estrutura ótima de solução (optimal substructure).
      - Uso de tabelas ou memória (memoization).
    - - Top-down (com memória)
        
        Resolve os subproblemas de forma recursiva.
        
        Antes de resolver um subproblema, verifica se ele já foi resolvido.
        
        Se já foi, retorna o valor armazenado.
        
        Se não foi, resolve e armazena o resultado em uma tabela
      - Bottom-up (iterativa)
        
        Resolve todos os subproblemas pequenos antes de resolver os maiores.
        
        Utiliza estruturas como vetores ou matrizes para armazenar os resultados parciais.
        
        Os subproblemas são resolvidos iterativamente, em ordem crescente de dificuldade.
- - - - Construir uma mst
      - Percorra a MST a partir de um nó qualquer registrando a ordem de visita
      - Eliminar nós repetidos exceto a origem
    - - Ordene os itens por valor/peso em ordem decrescente.
      - Vá colocando os itens na mochila nessa ordem:
        
        Se couber inteiro, coloque.
        
        Se não couber inteiro, coloque a fração que cabe.
      - Pare quando a mochila estiver cheia.