An Explanatory Comparison of Brute Force and Dynamic Programming Techniques to Solve the 0-1 Knapsack Problem


Authors : O.A Balogun; M.A Dosunmu; I.O Ibidapo

Volume/Issue : Volume 7 - 2022, Issue 2 - February

Google Scholar : http://bitly.ws/gu88

Scribd : https://bit.ly/3t09foA

DOI : https://doi.org/10.5281/zenodo.6345484

Abstract : During examination periods in schools, the demand on the use of examination rooms usually increases thus necessitating an optimal allocation of such rooms. This work seeks to explore an optimal way of allocating examination rooms by modeling the problem as a 0-1 Knapsack problem. Two approaches namely the Brute force and Dynamic programming techniques are used and implemented in Excel® and NetBeans® environments. The obtained results showed that dynamic programming approach yields a more optimal result than the Brute force implementation

Keywords : Knapsack, Dynamic Algorithm, Brute Force

During examination periods in schools, the demand on the use of examination rooms usually increases thus necessitating an optimal allocation of such rooms. This work seeks to explore an optimal way of allocating examination rooms by modeling the problem as a 0-1 Knapsack problem. Two approaches namely the Brute force and Dynamic programming techniques are used and implemented in Excel® and NetBeans® environments. The obtained results showed that dynamic programming approach yields a more optimal result than the Brute force implementation

Keywords : Knapsack, Dynamic Algorithm, Brute Force

Never miss an update from Papermashup

Get notified about the latest tutorials and downloads.

Subscribe by Email

Get alerts directly into your inbox after each post and stay updated.
Subscribe
OR

Subscribe by RSS

Add our RSS to your feedreader to get regular updates from us.
Subscribe