  We consider the maximization problem of monotone submodular functions under
an uncertain knapsack constraint. Specifically, the problem is discussed in the
situation that the knapsack capacity is not given explicitly and can be
accessed only through an oracle that answers whether or not the current
solution is feasible when an item is added to the solution. Assuming that
cancellation of the last item is allowed when it overflows the knapsack
capacity, we discuss the robustness ratios of adaptive policies for this
problem, which are the worst case ratios of the objective values achieved by
the output solutions to the optimal objective values. We present a randomized
policy of robustness ratio $(1-1/e)/2$, and a deterministic policy of
robustness ratio $2(1-1/e)/21$. We also consider a universal policy that
chooses items following a precomputed sequence. We present a randomized
universal policy of robustness ratio $(1-1/\sqrt[4]{e})/2$. When the
cancellation is not allowed, no randomized adaptive policy achieves a constant
robustness ratio. Because of this hardness, we assume that a probability
distribution of the knapsack capacity is given, and consider computing a
sequence of items that maximizes the expected objective value. We present a
polynomial-time randomized algorithm of approximation ratio
$(1-1/\sqrt[4]{e})/4-\epsilon$ for any small constant $\epsilon >0$.
