I am considering a special knapsack problem. The knapsack capacity is $M$. There are $N$ items ($N≥M$). The weight of each item is $1$. The profit for each item $i$ is $p(i) ≥ 0$. Thus, $M$ items can be filled in the sack. Different subsets of the items, $A$ (with $M$ items), can lead to different profits of the group $p(A)$.
My question is how can we get the distribution of the profit $p(A)$? Or is there any paper discussing the relation or the gap between the average value of $p(A)$ and the optimal value of $p(A)$?
Thanks in advance.
Set $V = \sum_{i=1}^N p(i)$ to be the value of all items and $$P(i) = \frac{p(i)}{V}.$$
Then $0 \leq P(i) \leq 1$ and $\sum_{i=1}^N P(i) = 1$, so $P$ is a discrete probability distribution on $\{1,2,\ldots, N\}$.
The profit is now $V \cdot P(A)$ for a subset $A$ of $\{1,2,\ldots, N\}$ with $M$ elements. There is quite some literature on discrete distributions and their behavior on subsets in most textbooks about (discrete) probability theory/statistics, so I would start looking there. It might, of course, help if $P$ has some nice properties, e.g. it is a well-known distribution.