Problema de la mochila
Páginas: 18 (4303 palabras)
Publicado: 10 de enero de 2014
Autora: MªÁngeles González Domínguez
Tutora: Yolanda Ortega Mallén
Trabajo de fin de grado
Facultad de CC Matemáticas
Curso 2011/2012
EL PROBLEMA DE LA MOCHILA Y SUS VARIANTES
2
EL PROBLEMA DE LA MOCHILA Y SUS VARIANTES
ABSTRACT
This project analyses the knapsack problem and some of its variants and explores several methods of resolving
them. In the first chapter, the problemand the main solving strategies are presented, together with the objectives of the
project. The second chapter is devoted to the subset sum problem, where the benefits are equal to the weights. While
the next chapter, the general case of the knapsack problem is explained in detail. Finally, the fourth chapter refers to
the variants in which one has several copies of each object. If the amountof copies is a finite, then it’s known as the
bounded knapsack problem, and if infinite, unbounded knapsack problem. Also it will be explained how these two
variants can be transformed into other types.
The main resolution strategies that we consider are: branch and bound, which explores the solution tree, and
dynamic programming algorithms, in which the solution is built iteratively. Thelatter algorithms can solve the allcapacities knapsack problem, too. In addition two approximation algorithms are given, one for the subset sum
problem and other for the general case.
For each algorithm presented here, the main ideas are explained and a Python’s implementation is given. This
implementation is used to run a collection of examples. These computational experiments are used to comparethe
efficiency of the algoritms.
3
EL PROBLEMA DE LA MOCHILA Y SUS VARIANTES
4
EL PROBLEMA DE LA MOCHILA Y SUS VARIANTES
ÍNDICE
Capítulo 1: Introducción .............................................................................................................................. 8
1.1. El problema de la mochila y sus variantes............................................................................................ 8
1.2. Métodos de resolución .......................................................................................................................... 9
1.3. Objetivos ............................................................................................................................................. 10
Capítulo 2: Suma de subconjuntos............................................................................................................ 12
2.1. Definición ........................................................................................................................................... 12
2.2. Algoritmos de programación dinámica ..............................................................................................12
2.2.1 Algoritmo de Bellman .................................................................................................................. 12
2.2.2 Algoritmo Primal-Dual ................................................................................................................ 14
2.2.3 Descomposición de Horowitz y Sahni......................................................................................... 16
2.2.4 Algoritmo de Balanceo ................................................................................................................ 18
2.3. Exploración exhaustiva ...................................................................................................................... 20
2.3.1 Vuelta atrás.................................................................................................................................. 20
2.3.2 Ramificación y poda .................................................................................................................... 21
2.3.3 Resultados .................................................................................................................................... 23
2.4. Algoritmos...
Tutora: Yolanda Ortega Mallén
Trabajo de fin de grado
Facultad de CC Matemáticas
Curso 2011/2012
EL PROBLEMA DE LA MOCHILA Y SUS VARIANTES
2
EL PROBLEMA DE LA MOCHILA Y SUS VARIANTES
ABSTRACT
This project analyses the knapsack problem and some of its variants and explores several methods of resolving
them. In the first chapter, the problemand the main solving strategies are presented, together with the objectives of the
project. The second chapter is devoted to the subset sum problem, where the benefits are equal to the weights. While
the next chapter, the general case of the knapsack problem is explained in detail. Finally, the fourth chapter refers to
the variants in which one has several copies of each object. If the amountof copies is a finite, then it’s known as the
bounded knapsack problem, and if infinite, unbounded knapsack problem. Also it will be explained how these two
variants can be transformed into other types.
The main resolution strategies that we consider are: branch and bound, which explores the solution tree, and
dynamic programming algorithms, in which the solution is built iteratively. Thelatter algorithms can solve the allcapacities knapsack problem, too. In addition two approximation algorithms are given, one for the subset sum
problem and other for the general case.
For each algorithm presented here, the main ideas are explained and a Python’s implementation is given. This
implementation is used to run a collection of examples. These computational experiments are used to comparethe
efficiency of the algoritms.
3
EL PROBLEMA DE LA MOCHILA Y SUS VARIANTES
4
EL PROBLEMA DE LA MOCHILA Y SUS VARIANTES
ÍNDICE
Capítulo 1: Introducción .............................................................................................................................. 8
1.1. El problema de la mochila y sus variantes............................................................................................ 8
1.2. Métodos de resolución .......................................................................................................................... 9
1.3. Objetivos ............................................................................................................................................. 10
Capítulo 2: Suma de subconjuntos............................................................................................................ 12
2.1. Definición ........................................................................................................................................... 12
2.2. Algoritmos de programación dinámica ..............................................................................................12
2.2.1 Algoritmo de Bellman .................................................................................................................. 12
2.2.2 Algoritmo Primal-Dual ................................................................................................................ 14
2.2.3 Descomposición de Horowitz y Sahni......................................................................................... 16
2.2.4 Algoritmo de Balanceo ................................................................................................................ 18
2.3. Exploración exhaustiva ...................................................................................................................... 20
2.3.1 Vuelta atrás.................................................................................................................................. 20
2.3.2 Ramificación y poda .................................................................................................................... 21
2.3.3 Resultados .................................................................................................................................... 23
2.4. Algoritmos...
Leer documento completo
Regístrate para leer el documento completo.