Distribution of a knapsack problem

Question

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.

Answer 1

The optimal value of $p(A)$ can easily be found by ordering the items by nonincreasing profits, and packing the first $M$ items into the knapsack. The average value of a packing is $(\sum_{i \in N}p_{i})/M$. As for the distribution of the profit, I intuitively don't see any other way than explicit enumeration, but I may be wrong about this.

Answer 2

I presume by "distribution" you're talking about a model where $M$ items are chosen randomly (with equal probabilities). The moment generating function of the profit
$ M(t) = \mathbb E[e^{tp(A)}]$ is the coefficient of $x^M$ in $${N \choose M}^{-1} \prod_{k=1}^N (1 + x e^{t p(k)})$$