<abstract xmlns="http://www.w3.org/1999/xhtml"><p>The subset sum problem is a basic problem in the field of theoretical computer science, especially in the complexity theory [3]. The input is a sequence of positive integers and a target positive integer. The task is to determine if there exists a subsequence of the input sequence with sum equal to the target integer. It is known that the problem is NP-hard [2] and can be solved by dynamic programming in pseudo-polynomial time [1]. In this article we formalize the recurrence relation of the dynamic programming.</p></abstract>

The subset sum problem is a basic problem in the field of theoretical computer science, especially in the complexity theory [3]. The input is a sequence of positive integers and a target positive integer. The task is to determine if there exists a subsequence of the input sequence with sum equal to the target integer. It is known that the problem is NP-hard [2] and can be solved by dynamic programming in pseudo-polynomial time [1]. In this article we formalize the recurrence relation of the dynamic programming.

Dynamic Programming for the Subset Sum Problem

Formalized Mathematics

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 License.

{"article-title":"Dynamic Programming for the Subset Sum Problem"}

The subset sum problem is a basic problem in the field of theoretical computer science, especially in the complexity theory [3]. The input is a sequence of...

Dynamic Programming for the Subset Sum Problem

Published Online: May 29, 2020

Page range: 89 - 92

Accepted: Jan 13, 2020

DOI: https://doi.org/10.2478/forma-2020-0007

Keywords
dynamic programming, subset sum problem, complexity theory

© 2020 Hiroshi Fujiwara et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 License.

Dynamic Programming for the Subset Sum Problem

Published Online: May 29, 2020

Page range: 89 - 92

Accepted: Jan 13, 2020

DOI: https://doi.org/10.2478/forma-2020-0007

Keywordsdynamic programming, subset sum problem, complexity theory

© 2020 Hiroshi Fujiwara et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 License.

Keywords
dynamic programming, subset sum problem, complexity theory