1
$\begingroup$

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.

$\endgroup$
1

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)})$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.