Enunciado:
Assuma que você tenha um problema cujas soluções
possuam um valor associado "c".
Suponha que você queira achar uma solução que
maximize o valor de "c". Lendo
artigos sobre o assunto, você descobriu que existe um algoritmo
que utiliza programação
dinâmica para encontrar esta solução. O
artigo onde você encontrou este algoritmo provava formalmente que
o algoritmo está correto, mas você tem a impressão
que um algoritmo guloso
poderia ser muito mais eficitente, embora você saiba que provar a
corretude do algoritmo guloso não será fácil.
Você resolve implementar ambos os algoritmos e comparar
algumas soluções para ver se a abordagem gulosa
não falha logo de cara. Que tipo de resultado mostraria que o
guloso NÃO funciona?
A) Tanto as soluções encontradas pelos algoritmos
quanto os valores de "c" para estas soluções são
diferentes para uma mesma entrada.
B) Tanto as soluções encontradas pelos algoritmos quanto
os valores de "c" para estas soluções são iguais
para uma mesma entrada.
C) Tanto as soluções encontradas pelos algoritmos quanto
os valores de "c" para estas soluções são iguais
para uma mesma entrada, mas o algoritmo guloso não resolve todos
os subproblemas que o algoritmo de programação
dinâmica resolve.
D) As soluções encontradas pelos algoritmos podem ser
diferentes, mas os valores de "c" para as soluções
sempres são iguais para uma mesma entrada.
E) NDA
Autor(a):José Augusto Amgarten Quitzau