# Knapsack with dependent profits (pairs of items)

I'm working on a problem which MAY be reduced to the following version of Knapsack:

Suppose two items $e_i$ and $e_j$ have profit $p_i$ and $p_j$ respectively. However, if both items are present in the knapsack, then for some $i$ and $j$, the combined profit of $e_i$ and $e_j$ is NOT $p_i+p_j$. It could be lower or higher. Note that in general, profits could be additive, but for some pairs of elements, our new rule holds, and we know in advance the value of $profit(\{e_i\} \cup \{e_j\})$ for such pairs. As always we want to maximize total profit.

So my question is, has work been done on such a variant of knapsack? Are there papers that can I read to better understand this formulation? I am not well-versed with the entire literature of Knapsack, and I tried to search for this but came up empty.

• Dynamic programming would still work, wouldn't it? Mar 8 '14 at 22:57
• there are two cases when adding e_j: a) e_i was already in the solution, then you have to check whether the weight increases or decreases. b) e_i was not in the solution, so now you have to check whether adding e_i is worth it, keeping in mind what elements you will be displacing.
– Ali
Mar 8 '14 at 23:03
• I don't think the objective function is precisely described. What exactly is the profit of a subset of given items? Mar 9 '14 at 2:36
• I just found out that what I was looking for is the Quadratic Knapsack problem.
– Ali
Mar 21 '14 at 21:00