The knapsack problem is a problem in combinatorial optimization that seeks to maximize the objective function \(\sum_{i = 1}^{n} v_ix_i\) subject to the constraints \(\sum_{i = 1}^{n} w_ix_i \leq W\) and \(x_i \in \{0, 1\}\), where \(\mathbf{x}, \mathbf{v} \in \mathbb{R}^{n}\) and \(W\) are provided. We consider the stochastic variant of this problem in which \(\mathbf{v}\) remains deterministic, but \(\mathbf{x}\)is an \(n\)-dimensional vector drawn uniformly at random from \([0, 1]^{n}\). We establish a sufficient condition under which the summation-bound condition is almost surely satisfied. Furthermore, we discuss the implications of this result on the deterministic problem.
This work has been published open access under Creative Commons Attribution License CC BY 4.0 , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Conditions, terms of use and publishing policy can be found at www.scienceopen.com .