For a given set $S = \{1, 2, ... , N \}$, each component $i\in S$ can be represented by a triple $(a_i, b_i, c_i)$. How can the following be solved? Any polynomial time algorithm exists?
$$\max_{S' \subseteq S} \left(\sum_{k\in S'} a_k \right) \cdot \left(\sum_{k\in S'} b_k \right) $$ subject to $$\sum_{k\in S'} c_k \leq C. $$
If the objective function is $\sum_{k\in S'} a_k$, it's KNAPSACK, and there's an efficient polynomial algorithm. I don't have any idea if there's any method to solve this type of problem.
You can solve this quadratic knapsack problem via integer linear programming as follows. For $i\in S$, let binary decision variable $x_i$ indicate whether $i\in S'$. For $1\le i < j \le N$, let binary decision variable $y_{i,j}$ represent $x_i x_j$. The problem is to maximize $$\sum_i a_i b_i x_i + \sum_{i < j} (a_i b_j + a_j b_i)y_{i,j}$$ subject to \begin{align} y_{i,j} &\le x_i &&\text{for all $i<j$} \tag1\\ y_{i,j} &\le x_j &&\text{for all $i<j$} \tag2\\ y_{i,j} &\ge x_i + x_j - 1 &&\text{for all $i<j$} \tag3\\ \sum_i c_i x_i &\le C \tag4 \end{align} If all $a_i$ and $b_i$ are nonnegative, you can omit $(3)$.