É uma técnica de otimização que é usada para resolver problemas complexos por meio da decomposição em subproblemas menores e independentes, resolvendo-os e combinando suas soluções para resolver o problema original.

Uma solução ótima para um problema pode ser encontrada a partir das soluções ótimas para seus subproblemas menores e independentes.

Assim evita a redundancia no calculo e reduz o tempo de execução do algoritmo

consiste em determinar a sequência de moedas que fornece o maior valor total possível, considerando que você só pode pegar uma moeda por vez e não pode pegar as moedas adjacentes.

o objetivo é encontrar a sequência de moedas que maximize a soma dos valores, sujeito à restrição de que não se pode pegar moedas adjacentes. Dado um vetor A de n moedas, cada uma com um valor associado

Defina um vetor V de tamanho n+1, onde V[i] representa o valor máximo que pode ser obtido usando as primeiras i moedas.

Inicialize V[0] = 0 e V[1] = A[1], ou seja, o valor máximo que pode ser obtido com nenhuma moeda é 0, e o valor máximo que pode ser obtido com uma moeda é o valor da primeira moeda.

Para i = 2 até n, calcule V[i] usando a seguinte fórmula: V[i] = max(V[i-1], V[i-2] + A[i]), ou seja, o valor máximo que pode ser obtido com as primeiras i moedas é o máximo entre o valor máximo que pode ser obtido com as primeiras i-1 moedas (ignorando a i-ésima moeda) e o valor máximo que pode ser obtido com as primeiras i-2 moedas mais o valor da i-ésima moeda.

O valor máximo que pode ser obtido usando todas as moedas é V[n].

determinar o menor número de moedas necessárias para formar um certo valor, dado um conjunto de moedas disponíveis.

dado um conjunto de n moedas, cada uma com um valor associado, e um valor total V, o objetivo é encontrar o menor número de moedas que somam exatamente V.

Defina um vetor C de tamanho V+1, onde C[i] representa o número mínimo de moedas necessárias para formar o valor i.

Inicialize C[0] = 0 e C[i] = infinito para i > 0, ou seja, o número mínimo de moedas para formar o valor 0 é 0, e o número mínimo de moedas para formar qualquer outro valor ainda não foi calculado.

Para cada moeda j no conjunto de moedas, para i = j até V, calcule C[i] usando a seguinte fórmula: C[i] = min(C[i], C[i-j]+1), ou seja, o número mínimo de moedas para formar o valor i é o mínimo entre o número mínimo de moedas necessário para formar o valor i usando as moedas anteriores e o número mínimo de moedas necessário para formar o valor i-j mais uma moeda de valor j.

O número mínimo de moedas necessário para formar o valor V é C[V].

a solução pode ser obtida em O(nV) tempo e O(V) espaço, onde n é o número de moedas e V é o valor total.

determinar o caminho que coleta o maior valor possível de moedas em uma grade retangular, dado que você começa na posição (1,1) e deve chegar à posição (m,n), e só pode se mover para baixo ou para a direita.

dado uma grade retangular m x n, cada célula contendo um valor associado à moeda, o objetivo é encontrar o caminho que coleta o maior valor possível de moedas, começando na posição (1,1) e terminando na posição (m,n), e só pode se mover para baixo ou para a direita.

Defina uma matriz A de tamanho m+1 x n+1, onde A[i][j] representa o valor máximo que pode ser obtido coletando moedas da célula (1,1) até a célula (i,j) da grade.

Inicialize A[1][1] = valor da célula (1,1) e A[i][1] = A[i-1][1] + valor da célula (i,1) e A[1][j] = A[1][j-1] + valor da célula (1,j), ou seja, o valor máximo que pode ser obtido na célula (1,1) é o valor da célula em si, e o valor máximo que pode ser obtido na primeira coluna e primeira linha é a soma acumulada do valor das células.

Para i = 2 até m, e para j = 2 até n, calcule A[i][j] usando a seguinte fórmula: A[i][j] = max(A[i-1][j], A[i][j-1]) + valor da célula (i,j), ou seja, o valor máximo que pode ser obtido na célula (i,j) é o máximo entre o valor máximo que pode ser obtido na célula acima ou à esquerda, mais o valor da célula (i,j) em si.

O valor máximo que pode ser obtido coletando moedas da célula (1,1) até a célula (m,n) é A[m][n].

são algoritmos que buscam encontrar uma solução próxima da solução ótima para problemas NP-difíceis em tempo polinomial.

Algoritmos de aproximação gulosa: esses algoritmos seguem uma estratégia gulosa, ou seja, a cada etapa escolhem a opção que parece ser a melhor no momento, sem considerar as consequências futuras. são frequentemente usados para resolver problemas de otimização que exigem soluções rápidas,

Algoritmos de aproximação baseados em programação linear: esses algoritmos buscam uma solução ótima para um problema linear, mas permitem que algumas variáveis assumam valores fracionários. usados para resolver problemas de otimização que podem ser formulados como um problema de programação linear inteira mista

Algoritmos de aproximação baseados em arredondamento: esses algoritmos arredondam as soluções fracionárias de um problema de programação linear para obter uma solução inteira. usados para resolver problemas de otimização de programação inteira

Algoritmos de aproximação baseados em heurísticas: esses algoritmos usam técnicas heurísticas para encontrar soluções próximas da solução ótima. usados para resolver problemas NP-difíceis que não possuem soluções polinomiais exatas conhecidas

objetivo é encontrar o menor caminho que visite todos os vértices de um grafo ponderado. O problema é conhecido por ser NP-difícil e não há algoritmos conhecidos para resolvê-lo em tempo polinomial para todas as entradas.

Algoritmo do vizinho mais próximo: este é um algoritmo guloso simples que começa em um vértice arbitrário e visita o vizinho mais próximo a cada etapa. Esse algoritmo é fácil de implementar e geralmente produz soluções razoáveis, mas não é garantido que produza a solução ótima.

Algoritmo 2-ópt: este algoritmo é uma heurística de busca local que tenta melhorar uma solução existente, removendo duas arestas cruzadas e as substituindo por duas arestas não cruzadas. Este algoritmo é rápido e geralmente produz soluções próximas à solução ótima, mas não é garantido que produza a solução ótima.

Algoritmo de Lin-Kernighan: este algoritmo é uma heurística de busca local que tenta melhorar uma solução existente, removendo uma sequência de arestas e as substituindo por uma nova sequência de arestas. Este algoritmo é muito eficiente e produz soluções muito próximas da solução ótima em muitos casos.

Algoritmo de Christofides: este algoritmo produz uma solução que é no máximo 1,5 vezes a solução ótima. O algoritmo começa encontrando uma árvore geradora mínima do grafo ponderado. Em seguida, adiciona-se um circuito euleriano na árvore, que visita cada aresta exatamente duas vezes. Finalmente, remove-se as repetições para obter um caminho hamiltoniano.

algoritmos de aproximação possam produzir soluções próximas à solução ótima, eles não são garantidos para encontrar a solução ótima.

escolha do algoritmo de aproximação depende do tamanho do grafo, da disponibilidade de recursos computacionais e da precisão desejada na solução.

problema de otimização combinatória que envolve escolher um subconjunto de itens de um conjunto de itens, cada um com um valor e peso associados, de modo a maximizar o valor total dos itens selecionados sem exceder a capacidade da mochila (que é limitada pelo peso máximo que ela pode carregar).

O problema da mochila é conhecido por ser NP-difícil, o que significa que não há algoritmos conhecidos para resolvê-lo em tempo polinomial para todas as entradas.

Algoritmo guloso, que seleciona os itens mais valiosos primeiro, até que a capacidade da mochila seja atingida. No entanto, esse algoritmo não leva em conta o peso dos itens, o que pode levar a soluções subótimas.

Algoritmo de programação dinâmica, que divide o problema em subproblemas menores e resolve-os de forma recursiva. No entanto, esse algoritmo pode ser impraticável para grandes conjuntos de itens.

Algoritmo de aproximação FPTAS (Fully Polynomial-Time Approximation Scheme). Esse algoritmo usa a técnica de escalonamento para reduzir o valor dos itens para que eles possam ser resolvidos em tempo polinomial usando programação dinâmica. O algoritmo FPTAS é garantido para produzir uma solução que é no mínimo (1 - ε) vezes a solução ótima, onde ε é um parâmetro de precisão especificado pelo usuário. Ele é um dos mais eficazes para esse problema

Algoritmo PTAS (Polynomial-Time Approximation Scheme), que é semelhante ao FPTAS, mas permite um parâmetro de precisão mais amplo e é mais geral em sua aplicação.

A escolha do algoritmo de aproximação depende do tamanho do conjunto de itens, da disponibilidade de recursos computacionais e da precisão desejada na solução.