Knapsack, nhưng chia cho tổng
Đối với một tập hợp nhất định $S = \{1, 2, ... , N \}$, mỗi thành phần $i\in S$ có thể được đại diện bởi $(a_i, b_i, c_i, w_i)$. Có bất kỳ kỹ thuật để giải quyết vấn đề sau đây?
$$\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)}$$ tùy thuộc vào $$\sum_{k\in S'} w_k \leq C. $$
Nếu hàm mục tiêu không chia cho $\left(\sum_{k\in S'} c_k \right)$, đó là QUADRATIC-KNAPSACK, có thể được giải quyết. Làm thế nào điều này có thể được giải quyết?
Trả lời
Đầu tiên hãy tuyến tính hóa tử số như được hiển thị trong câu trả lời của tôi cho NP khó (như KNAPSACK) - bất kỳ sơ đồ gần đúng nào? . Sau đó, áp dụng Charnes-Cooper như được hiển thị trong câu trả lời của tôi để Thực hiện một phép biến đổi Charnes-Cooper với ma trận và ràng buộc bằng không .