  We study a dynamic and stochastic knapsack problem in which a decision maker
is sequentially presented with items arriving according to a Bernoulli process
over $n$ discrete time periods. Items have equal rewards and independent
weights that are drawn from a known non-negative continuous distribution $F$.
The decision maker seeks to maximize the expected total reward of the items
that she includes in the knapsack while satisfying a capacity constraint and
while making terminal decisions as soon as each item weight is revealed. Under
mild regularity conditions on the weight distribution $F$, we prove that the
regret---the expected difference between the performance of the best sequential
algorithm and that of a prophet who sees all of the weights before making any
decision---is, at most, logarithmic in $n$. Our proof is constructive. We
devise a reoptimized heuristic that achieves this regret bound.

Probability;Discrete Mathematics;Data Structures and Algorithms;Optimization and Control