<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

Publicado en línea: 29 may 2020

Páginas: 89 - 92

Aceptado: 13 ene 2020

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

Palabras clave
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

Publicado en línea: 29 may 2020

Páginas: 89 - 92

Aceptado: 13 ene 2020

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

Palabras clavedynamic 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.

Palabras clave
dynamic programming, subset sum problem, complexity theory