Rucksack, aber durch Summation geteilt

Question

Für einen bestimmten Satz $S = \{1, 2, ... , N \}$, jede Komponente $i\in S$ kann dargestellt werden durch $(a_i, b_i, c_i, w_i)$. Gibt es eine Technik zur Lösung des folgenden Problems?

$$\max_{S' \subseteq S} \frac{ \left(\sum_{k\in S'} a_k \right) \cdot \left(\sum_{k\in S'} b_k \right) }{\left(\sum_{k\in S'} c_k \right)}$$ vorbehaltlich $$\sum_{k\in S'} w_k \leq C. $$

Wenn die Zielfunktion nicht durch geteilt wird $\left(\sum_{k\in S'} c_k \right)$, es ist QUADRATIC-KNAPSACK, der gelöst werden kann. Wie kann das gelöst werden?

Answer 1

Linearisieren Sie zuerst den Zähler wie in meiner Antwort auf NP hard (wie KNAPSACK) gezeigt - irgendein Approximationsschema? . Wenden Sie dann Charnes-Cooper an, wie in meiner Antwort auf Durchführen einer Charnes-Cooper-Transformation mit Matrizen und einer Null-Eins-Einschränkung gezeigt .