Please enable JavaScript.

Coggle requires JavaScript to display documents.

Programação Dinâmica, Algoritmos de Aproximação para Problemas NP-Difíceis…

- - - - Problema: Dado um conjunto de itens, cada um com um peso e um valor, determinar o número de cada item a ser incluído em uma coleção para que o peso total não exceda um limite e o valor total seja o maior possível.
      - Abordagem: Usar uma tabela para armazenar o valor máximo que pode ser alcançado com uma capacidade de mochila específica, considerando incrementalmente cada item.
      - Benefício: Garante que a solução encontrada seja ótima, evitando a avaliação de combinações de itens repetidamente.
  - - - Conceito: Usar armazenamento (memorização) para salvar os resultados de subproblemas já resolvidos, para que não precisem ser recalculados.
      - Aplicação: Essencial para reduzir a complexidade computacional em problemas onde subproblemas se repetem.
      - Exemplo: No problema da mochila, armazenar os valores máximos possíveis para subcapacidades específicas da mochila, reutilizando esses valores em cálculos posteriores.
- - - - Ordenação por Razão Valor/Peso: Ordene os itens pela razão valor/peso de forma decrescente.
      - Seleção Greedy: Adicione itens na mochila na ordem da razão até não ser mais possível adicionar o próximo item.
      - Ajuste Final: Se houver espaço remanescente, considere substituir o último item adicionado por uma combinação de itens menores que maximizem o valor sem exceder a capacidade.