  Knapsack problems are among the most fundamental problems in optimization. In
the Multiple Knapsack problem, we are given multiple knapsacks with different
capacities and items with values and sizes. The task is to find a subset of
items of maximum total value that can be packed into the knapsacks without
exceeding the capacities. We investigate this problem and special cases thereof
in the context of dynamic algorithms and design data structures that
efficiently maintain near-optimal knapsack solutions for dynamically changing
input. More precisely, we handle the arrival and departure of individual items
or knapsacks during the execution of the algorithm with worst-case update time
polylogarithmic in the number of items. As the optimal and any approximate
solution may change drastically, we only maintain implicit solutions and
support certain queries in polylogarithmic time, such as the packing of an item
and the solution value. While dynamic algorithms are well-studied in the
context of graph problems, there is hardly any work on packing problems and
generally much less on non-graph problems. Given the theoretical interest in
knapsack problems and their practical relevance, it is somewhat surprising that
Knapsack has not been addressed before in the context of dynamic algorithms and
our work bridges this gap.
