Dynamic Subset Sum

Given a collection of integers nin_i and a target sum tt, maintain xi{0,1}x_i\in \{0, 1\} satisfying xini=t\sum x_i n_i = t (or more generally maximizing xinit\sum x_i n_i \leq t) as values are inserted or deleted in the collection.

Parameters

  • SS: the set of integers
  • nn: the number of integers in the set
  • nn': the number of distinct elements in the set
  • tt: the target sum
  • σ\sigma: sum of elements in the set

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 1 of 1 algorithms

See more
Eppstein1997O(qtlogtlogn)O(qt log t log n)O(nt)

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table