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? – elexhobby 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
  • 10
    I don't think the objective function is precisely described. What exactly is the profit of a subset of given items? – Chandra Chekuri 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

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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