# Solve the online unweighted 0-1 knapsack problem efficiently

I have $$n$$ items and a bin of size $$B$$ units. Each item $$j$$ consumes $$w_j$$ units of $$B$$ when placed into the knapsack. The item appears one-by-one in an online fashion. Once item $$i$$ appears, we must either place it into the bin (irrevocably) or ignore it. The objective is to maximize the number of items placed into the bin. (All inputs are positive integers.)

The offline algorithm is easy: place the items in the order $$w_1\leq w_2\leq\cdots\leq w_n$$ until the bin is full.

How can I solve this problem in an online fashion? My approach is to randomize the choices: once item $$j$$ appears, place it into the bin with probability $$p_j$$ and ignore it otherwise.

• Do you know $w_j$ before-hand, but not the order? if the answer is no, do you know the distribution from where they are sampled or at least a bound on the maximal value? Also, do you know the how many elements are? All this information is important to define the optimal strategy. I think there exists a deterministic strategy that maximize the expected value of the number of items placed into the bin, independently from the answer to all my previous questions, it is just that the strategy is conditioned on those answers. – Marcelo Fornet Jun 16 at 0:17