|
Modified Greedy algorithm for Multidimensional Knapsack problem |
|---|---|
| รหัสดีโอไอ | |
| Creator | Ratee Bojaras |
| Title | Modified Greedy algorithm for Multidimensional Knapsack problem |
| Contributor | Sujaree Srisaard |
| Publisher | Faculty of Science, Ubon Ratchathani University |
| Publication Year | 2567 |
| Journal Title | Journal of Science and Science Education |
| Journal Vol. | 7 |
| Journal No. | 2 |
| Page no. | 260-271 |
| Keyword | Multidimensional knapsack problem, Combinatorial optimization, Integer linear programming, Greedy algorithm, The mean absolute percentage error |
| URL Website | https://so04.tci-thaijo.org/index.php/JSSE |
| Website title | Journal of Science and Science Education |
| ISSN | ISSN 2697-410X |
| Abstract | The Knapsack Problem (KP) is a combinatorial optimization problem that involves selecting items to be placed in a backpack in order to maximize the total value without exceeding the specified capacity. This problem can be formulated as an integer linear programming problem (ILP). In this study, we focused on the multidimensional knapsack problem (MDKP), which has multiple constraints and is more complex to solve. We experimented with different methods for sorting the benefits and evaluated the results using the solver function in Microsoft Excel. We considered 49 examples of 0-1 binary and pure integer knapsack problems. The experimental results showed that selecting items based on modified benefit values (profit/weight ratio) yielded better results than using the difference in benefits, as measured by the mean absolute percentage error (MAPE) across all samples. |
