I've been trying to theorize how to solve a certain type of problem for months now. Suppose you have a collection of $m$ pre-defined $(d+2)$-dimensional vectors like so:

$$(v, s, m_1, \dots, m_{d})$$

In this case $v$ represents the primary objective value, $s$ is the size of each object, each $m_i$ represents additional metadata. Also suppose we have some optimal values $m_1', \dots, m_{d}'$. The objective function is to select $k$ of these $m$ vectors to maximize

$$\sum_{i=1}^k v_i - (\overline{m_1} - m_1')^2 - (\overline{m_{d}} - m_{d}')^2$$

subject to $\sum_{i=1}^k s_i = n$. To be clear,

$$\overline{m_i} = \frac{\sum_{j=1}^k(s_j*m_{i_j})}{n}$$

In other words, the objective function is also being lowered by the squared distances between the mean of each $m_i$ selected and the "ideal" value $m_i'$. This is a special case of the knapsack problem with both an equality in place of the usual inequality and additional objective function elements. I know this is rather abstract, but is there any way to, if not find the optimal value, arrive at something close to it?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.