An efficient dynamic programming algorithm for the Unbounded Knapsack Problem
dc.contributor.advisor | Buriol, Luciana Salete | pt_BR |
dc.contributor.author | Moura, Leonardo Fernando dos Santos | pt_BR |
dc.date.accessioned | 2013-02-05T01:38:56Z | pt_BR |
dc.date.issued | 2013 | pt_BR |
dc.identifier.uri | http://hdl.handle.net/10183/66091 | pt_BR |
dc.description.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. | en |
dc.format.mimetype | application/pdf | pt_BR |
dc.language.iso | eng | pt_BR |
dc.rights | Open Access | en |
dc.subject | Algoritmos | pt_BR |
dc.subject | Unbounded knapsack problem | en |
dc.subject | Cutting stock problem | en |
dc.subject | Gramatica : Grafos | pt_BR |
dc.subject | Column generation | en |
dc.title | An efficient dynamic programming algorithm for the Unbounded Knapsack Problem | pt_BR |
dc.type | Trabalho de conclusão de graduação | pt_BR |
dc.identifier.nrb | 000870881 | pt_BR |
dc.degree.grantor | Universidade Federal do Rio Grande do Sul | pt_BR |
dc.degree.department | Instituto de Informática | pt_BR |
dc.degree.local | Porto Alegre, BR-RS | pt_BR |
dc.degree.date | 2013 | pt_BR |
dc.degree.graduation | Ciência da Computação: Ênfase em Ciência da Computação: Bacharelado | pt_BR |
dc.degree.level | graduação | pt_BR |
Este item está licenciado na Creative Commons License