Eftersom en multiset S av n positiva heltal och ett mål heltal t, den delmängd summa problemet är att besluta om det finns en delmängd av S som summerar upp till t. Vi presenterar en ny split-and-conquer algoritm som beräknar alla realizable delmängd summor upp till ett heltal u i O min{ ε nu, u 4/3, σ}, där σ är summan av alla element i S och O döljer polylogaritmiska faktorer. Detta resultat förbättras på standard dynamisk programmeringsalgoritm som körs i O(nu) tid. Såvitt vi vet är den nya algoritmen den snabbaste allmänna algoritmen för detta problem. Vi presenterar också en modifierad algoritm för cykliska grupper, som beräknar alla realizable delmängd summor inom gruppen i O min{ ε nm, m 5/4 } tid, där m är ordningen för gruppen.
I REF, författarna har infört en ny snabbare pseudo-polynom tid algoritm för Subset Sum problem att avgöra om det finns en delmängd av en given uppsättning S vars element summan till ett mål tal t. Deras föreslagna algoritm körs i O ( ε nt) tid, där n är storleken på set S. Deras strategi är baserad på en snabb Minkowski summa beräkning som utnyttjar strukturen av delmängd summor av små intervall.
A Faster Pseudopolynomial Time Algorithm for Subset Sum
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}