sfzsdsdfds

Trabalho de Análise de Algoritmos

Problema da Mochila
Felipe R. S. Barbosa, Flávio R. J. de Sousa, Leonardo dos Reis Vilela
Faculdade de Ciência da Computação – Universidade Federal de Uberlândia (UFU)
Uberlândia – MG – Brasil

[e-mail], [e-mail], [e-mail]

Resumo. Este artigo apresenta três soluções para o problema de encontrar um conjunto de itens nos quais a soma de seus pesos não exceda um valor dado e que a soma da suas utilidades seja a maior possível. O primeiro algoritmo é através da força bruta, o segundo algoritmo utiliza a técnica de programação dinâmica [CLR02] e o terceiro é um algoritmo de aproximação [CLR02] que utiliza a técnica de algoritmos gulosos [CLR02]. No decorrer do artigo discutiremos cada um destes.

1

Introdução

O problema da mochila consiste em dado um conjunto Cn de n itens, representados por Cn = {1, 2, ..., n}, cada item i ∈ C n tem um peso pi e utilidade ui (pi > 0 e ui > 0).
Determinar um subconjunto S ⊆ C n tal que a soma dos pesos dos elementos de S seja a maior possível.
Neste artigo iremos apresentar três soluções com algoritmos distintos para o problema da mochila.
O primeiro algoritmo apresenta a resolução mais óbvia, o qual é implementado utilizando a força bruta, ou seja, compara todas as possibilidades até encontrar a melhor.
Este algoritmo devolve a resposta correta, mas quando consideramos um conjunto relativamente grande de dados, o tempo gasto para obtermos a resposta é exponencialmente difícil de ser encontrada, logo o tempo deste algoritmo é exponencial.
O segundo algoritmo é o que utiliza o método da programação dinâmica. Este algoritmo também encontra a resposta correta com um tempo melhor que o anterior, porém se aumentarmos consideravelmente a capacidade da mochila, este algoritmo gastará um tempo muito maior do que o esperado. Assim dizemos que este algoritmo possui um tempo pseudo-polinomial, mas na sua essência ele é exponencial.
O terceiro e