On Unbounded Zero-One Knapsack With Discrete-Sized Objects
Kevin I.-J. Ho, Jie Wu, John Sum · International Journal of Computers and Applications · 2009
This paper presents an approximated solution for an unbounded knapsack problem where the sizes of objectsare discrete values:maxzn(M)=1n∑i=1npixis.t.∑i=1ncixi≤β0nxi∈{0,1}∀i=1,...,where pis are the profits that are uniformly distributed random variables in [0,1]. The sizes cis are discrete random variables which are distributed uniformly in {1/M, 2/M,…, (M-1)/M, 1}. zn(M) is the total profit to be maximized. Assuming that M is large, it is found that the optimal profit zn(M) is approximately equal to 2β0/3(1−0.3062(βM)−1) An example from auction is used to explain and illustrate the use of the derived solution in estimating the profit.