Item type |
学術雑誌論文 / Journal Article(1) |
公開日 |
2022-10-04 |
タイトル |
|
|
タイトル |
Dynamic Programming for the Subset Sum Problem |
言語 |
|
|
言語 |
eng |
DOI |
|
|
|
関連識別子 |
https://doi.org/10.2478/forma-2020-0007 |
|
|
関連名称 |
10.2478/forma-2020-0007 |
キーワード |
|
|
主題 |
dynamic programming, subset sum problem, complexity theory |
資源タイプ |
|
|
資源 |
http://purl.org/coar/resource_type/c_6501 |
|
タイプ |
journal article |
著者 |
Fujiwara, Hiroshi
Watari, Hokuto
Yamamoto, Hiroaki
|
信州大学研究者総覧へのリンク |
|
|
氏名 |
藤原, 洋志 |
|
URL |
https://soar-rd.shinshu-u.ac.jp/profile/ja.OmSVOFnU.html |
信州大学研究者総覧へのリンク |
|
|
氏名 |
山本, 博章 |
|
URL |
https://soar-rd.shinshu-u.ac.jp/profile/ja.ONfpOCSh.html |
引用 |
|
|
内容記述 |
FORMALIZED MATHEMATICS 28(1) : 89-92(2020) |
書誌情報 |
FORMALIZED MATHEMATICS
巻 28,
号 1,
p. 89-92,
発行日 2020-05-29
|
抄録 |
|
|
内容記述 |
The subset sum problem is a basic problem in the field of theoretical computer science, especially in the complexity theory. 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 and can be solved by dynamic programming in pseudo-polynomial time. In this article we formalize the recurrence relation of the dynamic programming. |
資源タイプ(コンテンツの種類) |
|
|
内容記述 |
Article |
ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1898-9934 |
権利 |
|
|
権利情報 |
© 2020 University of Białystok |
出版タイプ |
|
|
出版タイプ |
VoR |
|
出版タイプResource |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |