Comparison of dynamic programming and greedy algorithms and the way to solve 0-1 knapsack problem

Yitian Wu

doi:10.54254/2755-2721/5/20230666

Research Article

Open access

Published on 31 May 2023

Download pdf

Wu,Y. (2023). Comparison of dynamic programming and greedy algorithms and the way to solve 0-1 knapsack problem. Applied and Computational Engineering,5,631-636.

Export citation

Comparison of dynamic programming and greedy algorithms and the way to solve 0-1 knapsack problem

Yitian Wu *^,1,

¹ School of Computer Science, Central South University for Nationalities, Wuhan, Hubei Province, China, 430000

* Author to whom correspondence should be addressed.

https://doi.org/10.54254/2755-2721/5/20230666

Abstract

The 0-1 knapsack problem is widely used in reality and it belongs to NP-hard problems. Starting from the basic ideas and time complexity of the algorithm, this paper analyzes how to choose a strategy to solve the problem. This paper aims to solve practical problems and analyzes the 0-1 knapsack problem in combination with the real-life cargo delivery problem. Dynamic programming and greedy algorithms are used to tackle the problem respectively, and the advantages and disadvantages of two strategies are discussed, so as to analyze how to decide which strategy to adopt to solve the problem when encountering the 0-1 knapsack problem in an actual situation. In the face of large-scale problems, this paper suggests choosing greedy algorithm because it will save a lot of time. In the face of small-scale problems that require absolute solutions, this paper suggests choosing dynamic programming to solve the problem.

Keywords

0-1 Knapsack Problem, Dynamic Programming, Greedy Algorithm, Maximal Knapsack Packing, Optimal Solution.

View pdf

References

[1]. Martello, S., & Toth, P. (1990). Knapsack problems: Algorithms and computer implementations. Chichester: John Wiley & Sons.

[2]. Bellman, R. (1957). Dynamic programming. Princeton University Press.

[3]. Boyar, J., Epstein, L., Favrholdt, L. M., Kohrt, J. S., Larsen, K. S., Pedersen, M. M., et al. (2006). The maximum resource bin packing problem.Theoretical Computer Science, 362(1–3), 127–139.

[4]. Martello, S., & Toth, P. (1990). Knapsack problems: Algorithms and computer implementations. Chichester: John Wiley & Sons.

[5]. Glover, F. (2013). Advanced greedy algorithms and surrogate constraint methods for linear and quadratic knapsack and covering problems. European Journal of Operational Research, 230(2), 212–225.

[6]. Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack problems. Berlin: Springer.

[7]. Martello, S., Pisinger, D., & Toth, P. (1999). Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Science, 45, 414–424.

[8]. Pisinger, D. (1995). A minimal algorithm for the multiple-choice knapsack problem. European Journal of Operational Research, 83(2), 394–410.

[9]. Pisinger, D. (2007). The quadratic knapsack problem – a survey. Discrete Applied Mathematics, 155(5), 623–648.

[10]. Gai, L., & Zhang, G. (2009). Hardness of lazy packing and covering. Operations Research Letters, 37(2), 89–92.

Cite this article

Wu,Y. (2023). Comparison of dynamic programming and greedy algorithms and the way to solve 0-1 knapsack problem. Applied and Computational Engineering,5,631-636.

Data availability

The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.

Disclaimer/Publisher's Note

The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

About volume

Volume title: Proceedings of the 3rd International Conference on Signal Processing and Machine Learning

Conference website: http://www.confspml.org

ISBN：978-1-915371-57-7(Print) / 978-1-915371-58-4(Online)

Conference date: 25 February 2023

Editor：Omer Burak Istanbullu

Series: Applied and Computational Engineering

Volume number: Vol.5

ISSN：2755-2721(Print) / 2755-273X(Online)

© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license. Authors who publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See Open access policy for details).