W BIAŁYMSTOKU
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
