A modified Greedy algorithm for Multidimensional Knapsack problem
Article Sidebar
Main Article Content
บทคัดย่อ
ปัญหาถุงเป้เป็นปัญหาการหาค่าเหมาะที่สุดเชิงการจัด กล่าวคือ ต้องการเลือกของใส่ถุงเป้โดยเลือกของใส่ถุงให้มีมูลค่ารวมสูงสุดแต่ไม่เกินความจุที่กำหนด ซึ่งเป็นรูปแบบหนึ่งของปัญหากำหนดการเชิงจำนวนเต็ม งานวิจัยนี้ศึกษาปัญหาถุงเป้หลายมิติที่มีหลายเงื่อนไขและมีวิธีแก้ปัญหาซับซ้อนมากขึ้น โดยปรับปรุงการเรียงลำดับการเลือกของใส่ถุงเป้จากวิธีละโมบและนำผลเฉลยที่ได้ตรวจสอบกับผลเฉลยจากการใช้ฟังก์ชัน solver ในโปรแกรมสำเร็จรูปไมโครซอฟท์เอกซ์เซล จากการศึกษาปัญหาแบบ 0-1 และปัญหาแบบจำนวนเต็มแท้ทั้งหมด 49 ตัวอย่าง พบว่าการเรียงลำดับการเลือกของใส่ถุงเป้โดยปรับปรุงค่า benefit (อัตราส่วนกำไรต่อน้ำหนักสิ่งของ) ให้ผลเฉลยดีกว่าการใช้ค่า benefit แบบเดิม ทั้งนี้โดยพิจารณาจากค่าเฉลี่ยของร้อยละความผิดพลาดสัมบูรณ์จากจำนวนตัวอย่างทั้งหมด
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
วารสารวิทยาศาสตร์และวิทยาศาสตร์ศึกษา (JSSE) เป็นผู้ถือลิสิทธิ์บทความทุกบทความที่เผยแพร่ใน JSSE นี้ ทั้งนี้ ผู้เขียนจะต้องส่งแบบโอนลิขสิทธิ์บทความฉบับที่มีรายมือชื่อของผู้เขียนหลักหรือผู้ที่ได้รับมอบอำนาจแทนผู้เขียนทุกนให้กับ JSSE ก่อนที่บทความจะมีการเผยแพร่ผ่านเว็บไซต์ของวารสาร
แบบโอนลิขสิทธิ์บทความ (Copyright Transfer Form)
ทางวารสาร JSSE ได้กำหนดให้มีการกรอกแบบโอนลิขสิทธิ์บทความให้ครบถ้วนและส่งมายังกองบรรณาธิการในข้อมูลเสริม (supplementary data) พร้อมกับนิพนธ์ต้นฉบับ (manuscript) ที่ส่งมาขอรับการตีพิมพ์ ทั้งนี้ ผู้เขียนหลัก (corresponding authors) หรือผู้รับมอบอำนาจ (ในฐานะตัวแทนของผู้เขียนทุกคน) สามารถดำเนินการโอนลิขสิทธิ์บทความแทนผู้เขียนทั้งหมดได้ ซึ่งสามารถอัพโหลดไฟล์บทความต้นฉบับ (Manuscript) และไฟล์แบบโอนลิขสิทธิ์บทความ (Copyright Transfer Form) ในเมนู “Upload Submission” ดังนี้
1. อัพโหลดไฟล์บทความต้นฉบับ (Manuscript) ในเมนูย่อย Article Component > Article Text
2. อัพโหลดไฟล์แบบโอนลิขสิทธิ์บทความ (Copyright Transfer Form) ในเมนูย่อย Article Component > Other
ดาวน์โหลด ไฟล์แบบโอนลิขสิทธิ์บทความ (Copyright Transfer Form)
References
Al Etawi, N. A., and Aburomman, F. T. (2020). 0/1 knapsack problem: greedy vs. Dynamic-programming. International Journal of Advanced Engineering and Management Research, 5(2), 1-10.
Akçay, Y., Li, H. and Xu, S. H. (2007). Greedy algorithm for the general multidimensional knapsack problem. Annals of operations research, 150, 17–29.
Berberler, M. E., Guler, A., and Nurıyev, U. G. (2013). A genetic algorithm to solve the multidimensional knapsack problem. Mathematical and Computational Applications, 18(3), 486-494.
Buayen, P. and Werapun, J. (2018). Parallel time–space reduction by unbiased filtering for solving the 0/1-Knapsack problem. Journal of Parallel and Distributed Computing, 122, 195 - 208.
Durmuş, B., Güneri, O. I. and Incekırık, A. (2019). Comparison of Classic and Greedy Heuristic Algorithm Results in Integer Problems. Mugla Journal of Science and Technology, 5(1), 34-42.
Glover, F. (1965). A multiphase-dual algorithm for the zero-one integer programming problem. Operation Research, 13, 879–919.
Hassan, R., Cohanim, B., De Weck, O., and Venter, G. (2005, April). A comparison of particle swarm optimization and the genetic algorithm. In 46th AIAA/ASME/ASCE/AHS/ASC structures, structural dynamics and materials conference (pp. 2005-1897). Texas.
Irmeilyana, I., Bangun, P. B. J. and Izzah, H. (2017). Solution of Multiple Constraints Knapsack Problem (MCKP) by using Branch and Bound and Greedy Algorithm. Journal of Modeling and Optimization, 9(2), 112-119.
Koohathongsumrit, N. and Luangpaiboon, P. (2021), An Integrated FAHP–ZODP Approach for Strategic Marketing Information System Project Selection. Managerial and Decision Economics, 43(6), 1792-1809.
Mingo López, L. F., Gómez Blas, N., and Arteta Albert, A. (2018). Multidimensional knapsack problem optimization using a binary particle swarm model with genetic operations. Soft Computing, 22, 2567-2582.
Minsan, P. (2021). Comparing Methods of Optimization in Solver of Microsoft Excel 2007 and 2019: A Case Study of Statistical Models, The journal of KMUTNB, 31(3), 496-511.
Mohammad, A., Saleh, O., and Abdeen, R. A. (2006). Occurrences algorithm for string searching based on brute-force algorithm. Journal of Computer Science, 2(1), 82-85.
Multiple Knapsack Problems (2023). Retrieved 5 September 2023, from OR-library: http://people.brunel.ac.uk/
Pisinger, D. (1999). Linear Time Algorithms for Knapsack Problems with Bounded Weights. Journal of Algorithms. 33(1), 1-14.
Puchinger, J., Raidl, G. R., and Pferschy, U. (2010). The multidimensional knapsack problem: Structure and algorithms. INFORMS Journal on Computing, 22(2), 250-265.
Sajjan, S. P., Roogi, R., Badiger, V. and Amaragatti, S. (2014). A New Approach to Solve Knapsack Problem. Oriental Journal of Computer Science & Technology, 7(2), 219.
Senju, S. and Toyada, Y. (1968). An approach to linear programming problems with 0–1 variables, Management Science, 15(4), 196–207.
Varnamkhasti, M. J. (2012). Overview of the Algorithms for Solving the Multidimensional Knapsack Problems. Advanced Studies in Biology, 4(1), 37-47.