# Maximum-density multiple-choice knapsack problem

I am looking for work done on solving a problem (specifically I'm looking for an approximation algorithm) which is very similar to a combination of two variations of the knapsack problem: maximum-density knapsack problem and multiple-choice knapsack problem.

The problem is:

We have $$t$$ sets $$S_1,...,S_t$$ of elements, where each set is of size $$k$$: $$S_i=\{e_{i,1},e_{i,2},...,e_{i,k}\}$$. for each element $$e_{i,j}$$ there is a profit $$p_{i,j}$$ and a cost $$c_{i,j}$$. It holds that $$c_{i_1,j}=c_{i_2,j},i_1 \neq i_2$$(the cost is the same for each set it only depends on the element's index in the set) so let us denote $$c_{j}$$ from now on. Both the Profit and the Cost are monotonically increasing: $$c_{j_1} \leq c_{j_2} \text{ if } {j_1} \leq {j_2}$$ $$p_{i, j_1} \leq p_{i, j_2} \text{ if } {j_1} \leq {j_2}$$
The problem is to choose one element from each set to construct a set of $$t$$ elemets $${e_{1,j_1},e_{2,j_2},...,e_{t,j_t}}$$ with profits $${p_{1,j_1},p_{2,j_2},...,p_{t,j_t}}$$ and costs $${c_{j_1},c_{j_2},...,c_{j_t}}$$ such that the following exprssion is maximized: $$\frac{\sum_{i=1}^{t}p_{i,j_i}}{\sum_{i=1}^{t}c_{j_i}} = \frac{p_{1,j_1}+p_{2,j_2}+...+p_{t,j_t}}{{c_{j_1}+c_{j_2}+...+c_{j_t}}}$$
and the following expression holds for some constant $$0 \leq r \leq 1$$: $${\sum_{i=1}^{t}p_{i,j_i}} \geq r*{\sum_{i=1}^{t}p_{i,k}}$$

Intuitively, you need to maximize the ratio between the profit and the cost while having at least some portion of the profit.

As I said this problem can probably be reduced to a combination of maximum-density knapsack problem and multiple-choice knapsack problem, so any information on that (and not specifically on the problem I stated) can be helpful as well.

• Do you have a specific question about your situation? I see a specification of a problem and some statements, but I don't see a concrete question. We're a question-and-answer site, so we require you to articulate a specific answerable question about your situation. Do you want to know whether it is in NP? whether it is NP-complete? for an approximation algorithm? something else? – D.W. Apr 12 '20 at 21:09
• I want an approximation algorithm, sorry if that wasn't clear – Gilad Deutsch Apr 13 '20 at 16:12