  We study an online knapsack problem where the items arrive sequentially and
must be either immediately packed into the knapsack or irrevocably discarded.
Each item has a different size and the objective is to maximize the total size
of items packed. We focus on the class of randomized algorithms which initially
draw a threshold from some distribution, and then pack every fitting item whose
size is at least that threshold. Threshold policies satisfy many desiderata
including simplicity, fairness, and incentive-alignment. We derive two optimal
threshold distributions, the first of which implies a competitive ratio of
0.432 relative to the optimal offline packing, and the second of which implies
a competitive ratio of 0.428 relative to the optimal fractional packing. We
also consider the generalization to multiple knapsacks, where an arriving item
has a different size in each knapsack and must be placed in at most one. This
is equivalent to the AdWords problem where item truncation is not allowed. We
derive a randomized threshold algorithm for this problem which is
0.214-competitive. We also show that any randomized algorithm for this problem
cannot be more than 0.461-competitive, providing the first upper bound which is
strictly less than 0.5. This online knapsack problem finds applications in many
areas, like supply chain ordering, online advertising, and healthcare
scheduling, refugee integration, and crowdsourcing. We show how our optimal
threshold distributions can be naturally implemented in the warehouses for a
Latin American chain department store. We run simulations on their large-scale
order data, which demonstrate the robustness of our proposed algorithms.
