<p>This is a very interesting problem and I have been working on this for a while. The first thing to consider is that binary knapsack problem with dependent item weights/value is not trivial at all. You may consider using Bayesian networks, Markov models, and other similar techniques for solving this problem. Nonetheless, any practical approach to this problem has to make some assumptions either about the optimization model or its input. Here is an example of formulating the binary knapsack problem with value-dependent items. <a href="https://arxiv.org/pdf/1702.06662.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1702.06662.pdf</a></p>

<p>In this work, authors have proposed modeling the input (value-related dependencies) using fuzzy graphs and then using the proposed integer linear programming model to solve the optimization problem. An extended version of the work has been accepted for publication and will be soon available online. </p>

<p>Please do not hesitate to contact me if you needed further information. I can also provide you with the source code of the model if needed.  </p>
0/1 knapsack with dependent item weight?
<p>The standard 0/1 knapsack requires that the weight of every item is independent to others. Then DP is a efficient algorithm towards the solution. But now I met a similar but extensions of this problem, that </p>

<blockquote>
  <p>the weight of new items are dependent on previous items already in
  the knapsack.</p>
</blockquote>

<p><strong>For example</strong>, we have 5 items <code>a</code>, <code>b</code>, <code>c</code>, <code>d</code> and <code>e</code> with weight <code>w_a</code>, ..., <code>w_e</code>. item <code>b</code> and <code>c</code> have weight dependency.</p>

<p>When <code>b</code> is already in the knapsack, the weight of item <code>c</code> will be <em>smaller</em> than <code>w_c</code> because it can share some space with <code>b</code>, i.e. <code>weight(b&amp;c) &lt; w_b + w_c</code>. Symmetrically, when <code>c</code> is already in the knapsack, the weight of <code>b</code> will be smaller than <code>w_b</code>.</p>

<p>This uncertainty results a failure of original DP algorithm, since it depend on the correctness of previous iterations which may not correct now. I have read some papers about knapsack but they either have dependencies subjected to <em>profit</em> (<em>quadratic knapsack problem</em>), or have variable weight which follows a random distribution (<em>stochastic knapsack problem</em>). I have also aware of the previous question <a href="https://stackoverflow.com/questions/27928153/1-0-knapsack-variation-with-weighted-edges">1/0 Knapsack Variation with Weighted Edges</a>, but there is only a very generic answer available, and no answer about what is the name of this knapsack.</p>

<p><strong>One existing solution:</strong></p>

<p>I have also read one approximate solution in <a href="http://www.nec-labs.com/uploads/Documents/Data-Management/miso-sigmod2014.pdf" rel="noreferrer">a paper</a> about DBMS optimizations, where they <code>group the related items as one combined item for knapsack</code>. If use this technique into our example, the items for knapsack will be <code>a</code>, <code>bc</code>, <code>d</code>, <code>e</code>, therefore there is no more dependencies between any two of these four items. However it is easy to construct an example that does not get optimal result, like when <code>an item with "small weight and benefit" is grouped with another item with "large weight and benefit"</code>. In this example, the "small" item should not be selected in solution, but is selected together with the "large" item.</p>

<p><strong>Question:</strong></p>

<p>Is there any kind of efficient solving techniques that can get optimal result, or at least with some error guarantee? Or am I taking the wrong direction for modelling this problem?</p>