An efficient dynamic programming algorithm for the Unbounded Knapsack Problem
![Thumbnail](/bitstream/handle/10183/66091/000870881.pdf.jpg?sequence=3&isAllowed=y)
Visualizar/abrir
Data
2013Orientador
Nível acadêmico
Graduação
Assunto
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 ...
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. ...
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.
Coleções
Este item está licenciado na Creative Commons License
![](/themes/Mirage2Novo//images/lume/cc.png)