<p>This is a very interesting problem. But cannot be addressed in its general form. Assumptions need to be made in relation to the application domain. You may find the attached paper useful. The paper assumes strengths of value-related dependencies are imprecise.</p>

<p>please see this: <a href="https://link.springer.com/chapter/10.1007/978-3-319-63004-5_12" rel="nofollow noreferrer">https://link.springer.com/chapter/10.1007/978-3-319-63004-5_12</a></p>

CC BY-SA 3.0
2017-11-10T01:57:45.940Z
2017-11-10T01:57:45.940Z
user47457
<p>I'm working on a problem which MAY be reduced to the following version of Knapsack:</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-03-08T22:57:24.547Z
Dynamic programming would still work, wouldn't it?
elexhobby
CC BY-SA 3.0
2014-03-08T23:03:54.493Z
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
CC BY-SA 3.0
2014-03-09T02:36:32.887Z
I don't think the objective function is precisely described. What exactly is the profit of a subset of given items?
Chandra Chekuri
CC BY-SA 3.0
2014-03-21T21:00:08.597Z
I just found out that what I was looking for is the Quadratic Knapsack problem.
Ali
<ds.algorithms><optimization>
Knapsack with dependent profits (pairs of items)
Ali
# Knapsack with dependent profits (pairs of items)

(Asked by: username_0 on 2014-03-08)

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.

**Tags:** ds.algorithms, optimization
> **Comments:**
> **username_1**: Dynamic programming would still work, wouldn't it?  
> **username_0**: 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.  
> **username_2**: I don't think the objective function is precisely described. What exactly is the profit of a subset of given items?  
> **username_0**: I just found out that what I was looking for is the Quadratic Knapsack problem.  

---

## 1 answers

### Answer by username_3 on 2017-11-10. Score: 0

This is a very interesting problem. But cannot be addressed in its general form. Assumptions need to be made in relation to the application domain. You may find the attached paper useful. The paper assumes strengths of value-related dependencies are imprecise.

please see this: <https://link.springer.com/chapter/10.1007/978-3-319-63004-5_12>


---

