Show simple item record

An efficient dynamic programming algorithm for the Unbounded Knapsack Problem

dc.contributor.advisorBuriol, Luciana Saletept_BR
dc.contributor.authorMoura, Leonardo Fernando dos Santospt_BR
dc.date.accessioned2013-02-05T01:38:56Zpt_BR
dc.date.issued2013pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/66091pt_BR
dc.description.abstractThis 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.mimetypeapplication/pdfpt_BR
dc.language.isoengpt_BR
dc.rightsOpen Accessen
dc.subjectAlgoritmospt_BR
dc.subjectUnbounded knapsack problemen
dc.subjectCutting stock problemen
dc.subjectGramatica : Grafospt_BR
dc.subjectColumn generationen
dc.titleAn efficient dynamic programming algorithm for the Unbounded Knapsack Problempt_BR
dc.typeTrabalho de conclusão de graduaçãopt_BR
dc.identifier.nrb000870881pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Informáticapt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2013pt_BR
dc.degree.graduationCiência da Computação: Ênfase em Ciência da Computação: Bachareladopt_BR
dc.degree.levelgraduaçãopt_BR


Files in this item

Thumbnail
Name:
000870881.pdf
Size:
413.4Kb
Format:
PDF
Description:
Texto completo (inglês)
View/Open
   

This item is licensed under a Creative Commons License

Show simple item record