{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T07:39:59Z","timestamp":1762069199719,"version":"build-2065373602"},"reference-count":43,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T00:00:00Z","timestamp":1664496000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100007120","name":"School of Science, King Mongkut\u2019s Institute of Technology Ladkrabang (KMITL)","doi-asserted-by":"publisher","award":["CW-011-2\/2562"],"award-info":[{"award-number":["CW-011-2\/2562"]}],"id":[{"id":"10.13039\/501100007120","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The multiple knapsack problem (0\/1-mKP) is a valuable NP-hard problem involved in many science-and-engineering applications. In current research, there exist two main approaches: 1. the exact algorithms for the optimal solutions (i.e., branch-and-bound, dynamic programming (DP), etc.) and 2. the approximate algorithms in polynomial time (i.e., Genetic algorithm, swarm optimization, etc.). In the past, the exact-DP could find the optimal solutions of the 0\/1-KP (one knapsack, n objects) in O(nC). For large n and massive C, the unbiased filtering was incorporated with the exact-DP to solve the 0\/1-KP in O(n + C\u2032) with 95% optimal solutions. For the complex 0\/1-mKP (m knapsacks) in this study, we propose a novel research track with hybrid integration of DP-transformation (DPT), exact-fit (best) knapsack order (m!-to-m2 reduction), and robust unbiased filtering. First, the efficient DPT algorithm is proposed to find the optimal solutions for each knapsack in O([n2,nC]). Next, all knapsacks are fulfilled by the exact-fit (best) knapsack order in O(m2[n2,nC]) over O(m![n2,nC]) while retaining at least 99% optimal solutions as m! orders. Finally, robust unbiased filtering is incorporated to solve the 0\/1-mKP in O(m2n). In experiments, our efficient 0\/1-mKP reduction confirmed 99% optimal solutions on random and benchmark datasets (n \u03b4 10,000, m \u03b4 100).<\/jats:p>","DOI":"10.3390\/a15100366","type":"journal-article","created":{"date-parts":[[2022,10,7]],"date-time":"2022-10-07T22:47:27Z","timestamp":1665182847000},"page":"366","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Efficient 0\/1-Multiple-Knapsack Problem Solving by Hybrid DP Transformation and Robust Unbiased Filtering"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9721-9153","authenticated-orcid":false,"given":"Patcharin","family":"Buayen","sequence":"first","affiliation":[{"name":"Department of Computer Science, Faculty of Science, King Mongkut\u2019s Institute of Technology Ladkrabang, Bangkok 10520, Thailand"}]},{"given":"Jeeraporn","family":"Werapun","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Faculty of Science, King Mongkut\u2019s Institute of Technology Ladkrabang, Bangkok 10520, Thailand"}]}],"member":"1968","published-online":{"date-parts":[[2022,9,30]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/j.jpdc.2018.08.003","article-title":"Parallel time-space reduction by unbiased filtering for solving the 0\/1-knapsack problem","volume":"122","author":"Buayen","year":"2018","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1016\/j.ijpe.2011.12.011","article-title":"Resource management in software as a service using the knapsack problem model","volume":"141","author":"Aisopos","year":"2013","journal-title":"Int. J. Prod. Econ."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/j.future.2008.07.006","article-title":"Resource allocation on computational grids using a utility model and the knapsack problem","volume":"25","author":"Vanderster","year":"2009","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"12415","DOI":"10.1016\/j.eswa.2011.04.022","article-title":"A capital budgeting problem for preventing workplace mobbing by using analytic hierarchy process and fuzzy 0-1 bidimensional knapsack model","volume":"38","author":"Bas","year":"2011","journal-title":"Expert Syst. Appl."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.cor.2010.10.023","article-title":"A knapsack problem as a tool to solve the production planning problem in small foundries","volume":"39","author":"Camargo","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1613\/jair.2106","article-title":"Bin completion algorithms for multicontainer packing, knapsack, and covering problems","volume":"28","author":"Fukunaga","year":"2007","journal-title":"J. Artif. Intell. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"842","DOI":"10.1016\/j.ejor.2015.10.014","article-title":"Robust optimization of the 0-1 knapsack problem: Balancing risk and return in assortment optimization","volume":"250","author":"Rooderkerk","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"6819","DOI":"10.1016\/j.eswa.2015.04.027","article-title":"Delay optimization using Knapsack algorithm for multimedia traffic over MANETs","volume":"42","author":"Ahmad","year":"2015","journal-title":"Expert Syst. Appl."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jpdc.2015.07.008","article-title":"A Knapsack-based buffer management strategy for delay-tolerant networks","volume":"86","author":"Wang","year":"2015","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.eswa.2015.10.006","article-title":"Combination of genetic network programming and knapsack problem to support record clustering on distributed databases","volume":"46","author":"Wedashwara","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Kellerer, H., Pferschy, U., and Pisinger, D. (2004). Dynamic Programming. Knapsack Problem, Springer.","DOI":"10.1007\/978-3-540-24777-7"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"2625","DOI":"10.1016\/j.cor.2013.05.005","article-title":"Exact solution of the robust knapsack problem","volume":"40","author":"Monaci","year":"2013","journal-title":"Comput. Oper. Res."},{"key":"ref_13","first-page":"6921","article-title":"Dynamic programming based algorithms for the discounted {0-1} knapsack problem","volume":"218","author":"Rong","year":"2012","journal-title":"Appl. Math. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2913","DOI":"10.1016\/j.camwa.2011.07.067","article-title":"A two state reduction based dynamic programming algorithm for the bi-objective 0-1 knapsack problem","volume":"62","author":"Rong","year":"2011","journal-title":"Comput. Math. Appl."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.ejor.2013.11.032","article-title":"Dynamic programming algorithms for the bi-objective integer knapsack problem","volume":"236","author":"Rong","year":"2014","journal-title":"Eur. J. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1016\/j.endm.2010.05.079","article-title":"A new lagrangian based branch and bound algorithm for the 0-1 knapsack problem","volume":"36","author":"Cunha","year":"2010","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1883","DOI":"10.1016\/j.tcs.2009.12.004","article-title":"On exponential time lower bound of knapsack under backtracking","volume":"411","author":"Li","year":"2010","journal-title":"Theor. Comput. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1016\/S0167-6377(02)00222-5","article-title":"Average-case analysis of a greedy algorithm for the 0\/1 knapsack problem","volume":"31","author":"Calvin","year":"2003","journal-title":"Oper. Res. Lett."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1774","DOI":"10.1016\/j.asoc.2012.11.048","article-title":"Chemical reaction optimization with greedy strategy for the 0-1 knapsack problem","volume":"13","author":"Truong","year":"2013","journal-title":"Appl. Soft Comput."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1130","DOI":"10.1287\/opre.28.5.1130","article-title":"An algorithm for large zero-one knapsack problems","volume":"28","author":"Balas","year":"1980","journal-title":"Oper. Res."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1016\/j.ejor.2017.06.005","article-title":"Adaptive kernal search: A heuristic for solving mixed integer linear programs","volume":"263","author":"Guastaroba","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/j.eswa.2016.01.055","article-title":"Taming the 0\/1 knapsack problem with monogamous pairs genetic algorithm","volume":"54","author":"Lim","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Sachdeva, C., and Goel, S. (2014, January 9\u201311). An improved approach for solving 0\/1 knapsack problem in polynomial time using genetic algorithms. Proceedings of the IEEE International Conference on Recent Advances and Innovations in Engineering, Jaipur, India.","DOI":"10.1109\/ICRAIE.2014.6909284"},{"key":"ref_24","first-page":"11042","article-title":"A modified binary particle swarm optimization for knapsack problems","volume":"218","author":"Bansal","year":"2012","journal-title":"Appl. Math. Comput."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1016\/j.asoc.2014.02.010","article-title":"Shuffled frog leaping algorithm and its application to 0\/1 knapsack problem","volume":"19","author":"Bhattacharjee","year":"2014","journal-title":"Appl. Soft Comput."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.swevo.2014.10.002","article-title":"Soccer league competition algorithm for solving knapsack problem","volume":"20","author":"Moosavian","year":"2015","journal-title":"Swarm Evol. Comput."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/j.proenv.2011.12.025","article-title":"Comparative study of several intelligent algorithms for knapsack problem","volume":"11","author":"Zhang","year":"2011","journal-title":"Procedia Environ. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1556","DOI":"10.1016\/j.asoc.2010.07.019","article-title":"Solving 0-1 knapsack problem by novel global harmony search algorithm","volume":"11","author":"Zou","year":"2011","journal-title":"Appl. Soft Comput."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.asoc.2015.11.045","article-title":"Solving 0-1 knapsack problem by greedy degree and expectation efficiency","volume":"41","author":"Lv","year":"2016","journal-title":"Appl. Soft Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/j.swevo.2016.02.006","article-title":"Gursaran, Quantum inspired social evolution (QSE) algorithm for 0-1 knapsack problem","volume":"29","author":"Pavithr","year":"2016","journal-title":"Swarm Evol. Comput."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Zhao, J., Huang, T., Pang, F., and Liu, Y. (2009, January 14\u201317). Genetic algorithm based on greedy strategy in the 0-1 knapsack problem. Proceedings of the 2009 Third International Conference on Genetic and Evolutionary Computing, Guilin, China.","DOI":"10.1109\/WGEC.2009.43"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1016\/j.asoc.2015.10.043","article-title":"An improved monkey algorithm for 0-1 knapsack problem","volume":"38","author":"Zhou","year":"2016","journal-title":"Appl. Soft Comput."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Sanchez-Diaz, X., Ortiz-Bayliss, J.C., Amaya, I., Cruz-Duarte, J.M., Conant-Pablos, S.E., and Terashima-Marin, H. (2021). A feature-independent hyper-heuristic approach for solving the knapsack problem. Appl. Sci., 11.","DOI":"10.3390\/app112110209"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"886","DOI":"10.1016\/j.ejor.2018.10.043","article-title":"Mathematical models and decomposition methods for the multiple knapsack problem","volume":"274","author":"Delorme","year":"2019","journal-title":"Eur. J. Oper. Res."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10479-009-0660-y","article-title":"A branch-and-bound algorithm for hard multiple knapsack problems","volume":"184","author":"Fukunaga","year":"2011","journal-title":"Ann. Oper. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"102004","DOI":"10.1016\/j.omega.2018.11.013","article-title":"Algorithmic approaches to the multiple knapsack assignment problem","volume":"90","author":"Martello","year":"2020","journal-title":"Omega"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"2017","DOI":"10.1016\/j.cor.2010.02.002","article-title":"Kernal search: A general heuristic for the multi-dimensional knapsack problem","volume":"37","author":"Angelelli","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.engappai.2016.05.006","article-title":"A hybrid quantum particle swarm optimization for the multidimensional knapsack problem","volume":"55","author":"Haddar","year":"2016","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.asoc.2016.11.023","article-title":"An improved fruit fly optimization algorithm for solving the multidimensional knapsack problem","volume":"50","author":"Meng","year":"2017","journal-title":"Appl. Soft Comput."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1016\/j.asoc.2015.06.004","article-title":"A human learning optimization algorithm and its application to multi-dimensional knapsack problems","volume":"34","author":"Wang","year":"2015","journal-title":"Appl. Soft Comput."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1016\/j.asoc.2016.02.027","article-title":"Binary artificial algae algorithm for multidimensional knapsack problems","volume":"43","author":"Zhang","year":"2016","journal-title":"Appl. Soft Comput."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2016.11.042","article-title":"An iterative pseudo-gap enumeration approach for the multidimensional multiple-choice knapsack problem","volume":"260","author":"Gao","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Wang, Y., and Wang, W. (2021). Quantum-inspired differential evolution with gray wolf optimizer for 0-1 knapsack problem. Mathematics, 9.","DOI":"10.3390\/math9111233"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/10\/366\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:44:41Z","timestamp":1760143481000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/10\/366"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,30]]},"references-count":43,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2022,10]]}},"alternative-id":["a15100366"],"URL":"https:\/\/doi.org\/10.3390\/a15100366","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,9,30]]}}}