Repositório Digital

A- A A+

An efficient dynamic programming algorithm for the Unbounded Knapsack Problem

.

An efficient dynamic programming algorithm for the Unbounded Knapsack Problem

Mostrar registro completo

Estatísticas

Título An efficient dynamic programming algorithm for the Unbounded Knapsack Problem
Autor Moura, Leonardo Fernando dos Santos
Orientador Buriol, Luciana Salete
Data 2013
Nível Graduação
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Ciência da Computação: Ênfase em Ciência da Computação: Bacharelado.
Assunto Algoritmos
Gramatica : Grafos
[en] Column generation
[en] Cutting stock problem
[en] Unbounded knapsack problem
Abstract This report describes an algorithm for the Unbounded Knapsack Problem based on the algorithm EDUK (Efficient Dynamic Programming for the Unbounded Knapsack Problem). EDUK takes advantage of the problem properties of dominance and periodicity to speed up computation. This algorithm is compared with other implementations and it is tested both with randomly generated instances and with instances generated from a delayed column generation for the Cutting Stock Problem. This report also contains an analysis of unbounded knapsack instances.
Tipo Trabalho de conclusão de graduação
URI http://hdl.handle.net/10183/66091
Arquivos Descrição Formato
000870881.pdf (423.3Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.