On Unbounded Zero-One Knapsack with Discrete-Sized Objects

摘要

This paper presents an approximated solution for an unbounded knapsack problem where the sizes of objects are discrete values:rnmax z_n(M) = 1 ∑~n_(I=1) P_I x_IrnS.t. ∑~n_(I=1) c_I x_I ≤ β_0 nrnx_I ∈ {0,1} any I = 1,…,nrnwhere p_I s are the profits that are uniformly distributed random variables in [0,1]. The sizes c,;s are discrete random variables which are distributed uniformly in {1/M, 2/M, …,(M- 1)/M, 1}. Z_n(M) is the total profit to be maximized. Assuming that hi is large, it is found that the optimal profit z_n(M) is approximately equal to (2β_0/3)~(1/2)(1 - 0.3062((β_0)~(1/2)M)~(-1)). An example from auction is used to explain and illustrate the use of the derived solution in estimating the profit.