Outro Agoritmo guloso e mochila fracionária

josinei dornelas · 19 de agosto de 2022

Bom dia, não estou conseguindo resolver esse exercício... Travei e não consigo seguir com o raciocínio.

Considere o problema de troca para n centavos de Real usando o menor número de moedas possível. Suponha que o valor de cada moeda é um inteiro.

Suponha que as moedas disponíveis tem as denominações 1, 5, 10, 25. Forneça um algoritmo guloso para este caso e prove sua correção.

Suponha que as moedas disponíveis têm denominações que são potências de c : c0 , c1, ..., ck , para inteiros c > 1 e K ≥ 1. Mostre que o algoritmo guloso sempre encontra uma solução ótima neste caso.

Forneça um conjunto de denominação de moedas para o qual o algoritmo guloso não garante que a solução devolvida seja ótima. Inclua a moeda de 1 centavo no seu conjunto para que a troca seja possível para qualquer valor de n.

Forneça um algoritmo com consumo de tempo O(nk) que faça a troca para qualquer conjunto com k denominações diferentes de moedas, assumindo que uma delas é a de 1 centavo.

Mostre como resolver o problema da mochila fracionaria em tempo O(n), sem supor que os inteiros em v[1..n] e w[1..n] são limitados (i.e o uso de RADIXSORT não é uma solução apropriada).

Seja S[1..n] uma sequência (de inteiros). Uma sequência T[1..m] é subsequência de S se existem índices i1, i2, ..., im com 1 ≤ i1 < i2 < ... < im ≤ n tais que T[j] = S[ij]. Uma sequência T de S é crescente se T[1] ≤ T[2] ≤ ... ≤ T[m]. Uma subsequência crescente T é máxima (= mais longa) se o valor de m é o maior possível. Denote por (LIS) o problema de determinar uma subsequência crescente máxima para S.

Descreva e prove a subestrutura ótima dos subproblemas de (LIS).

Obtenha uma recorrência para uma solução recursiva simples de (LIS) e analise o tempo requerido por ela.

Forneça um algoritmo em programação dinâmica que resolve (LIS) em tempo O(n2) .

Continuando o exercício anterior, forneça um algoritmo em programação dinâmica que resolve (LIS) em tempo O(n log n).