Discrete optimisation in 5 variables

Question

I need to solve the following optimisation problem and I can't come up with any solutions. Is there any algorithm to solve this type of problem. I tried to think of a greedy algorithm or brute force, but couldn't solve it.

Input :
$ n_1, n_2, n_3, n_4, n_5$ : Positive integers
$ a_1, a_2, a_3, a_4, a_5 $ : Positive integers
$ p_1, p_2, p_3, p_4, p_5 $ : Positive integers
$ Q $ : Positive integer

Output : $ m_1, m_2, m_3, m_4, m_5$ : Non- negative integers

Minimize : $ \sum_{i=1}^{5}{m_i a_i p_i}$

Constraints :
$ \forall i : m_i \geq n_i $ OR $ m_i = 0 $
$ \sum_{i=1}^{5}{m_i a_i} \geq Q$

Answer 1

First of all, we can enumerate over all 32 possibilities of which of the two alternatives is chosen for each $m_i$ (whether $m_i \geq n_i$ or $m_i = 0$). We will analyze, for simplicity, the case where $m_i \geq n_i$ for all $i$. Let $\mu_i = m_i - n_i$, so that $\mu_i$ is some arbitrary non-negative integer. We now want to minimize the quantity $\sum_i \mu_i a_i p_i$ under the constraint $\sum_i \mu_i a_i \geq P$ (where $P$ is a function of other known parameters).

You can now reduce your problem to KNAPSACK as described in a question on cstheory.