Proszę używać tego identyfikatora do cytowań lub wstaw link do tej pozycji:
http://hdl.handle.net/11320/9225
Tytuł: | Dynamic Programming for the Subset Sum Problem |
Autorzy: | Fujiwara, Hiroshi Watari, Hokuto Yamamoto, Hiroaki |
Słowa kluczowe: | dynamic programming subset sum problem complexity theory |
Data wydania: | 2020 |
Data dodania: | 10-cze-2020 |
Wydawca: | DeGruyter Open |
Źródło: | Formalized Mathematics, Volume 28, Issue 1, Pages 89-92 |
Abstrakt: | 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. |
Afiliacja: | Hiroshi Fujiwara - Shinshu University, Nagano, Japan Hokuto Watari - Nagano Electronics Industrial Co., Ltd., Chikuma, Japan Hiroaki Yamamoto - Shinshu University, Nagano, Japan |
Sponsorzy: | This work was supported by JSPS KAKENHI Grant Numbers JP16K00033, JP17K00013 and JP17K00183. |
URI: | http://hdl.handle.net/11320/9225 |
DOI: | 10.2478/forma-2020-0007 |
ISSN: | 1426-2630 |
e-ISSN: | 1898-9934 |
Typ Dokumentu: | Article |
metadata.dc.rights.uri: | http://creativecommons.org/licenses/by-sa/3.0/pl/ |
Występuje w kolekcji(ach): | Formalized Mathematics, 2020, Volume 28, Issue 1 |
Pliki w tej pozycji:
Plik | Opis | Rozmiar | Format | |
---|---|---|---|---|
forma_2020_28_01_0007.pdf | 225,56 kB | Adobe PDF | Otwórz |
Pozycja ta dostępna jest na podstawie licencji Licencja Creative Commons CCL