  The online knapsack problem is a classic online resource allocation problem
in networking and operations research. Its basic version studies how to pack
online arriving items of different sizes and values into a capacity-limited
knapsack. In this paper, we study a general version that includes item
departures, while also considering multiple knapsacks and multi-dimensional
item sizes. We design a threshold-based online algorithm and prove that the
algorithm can achieve order-optimal competitive ratios. Beyond worst-case
performance guarantees, we also aim to achieve near-optimal average performance
under typical instances. Towards this goal, we propose a data-driven online
algorithm that learns within a policy-class that guarantees a worst-case
performance bound. In trace-driven experiments, we show that our data-driven
algorithm outperforms other benchmark algorithms in an application of online
knapsack to job scheduling for cloud computing.
