0
$\begingroup$

I want to find the possible values for {$x_i$} for given that I know $y$, {$p_i$} and the sum of $x_i$. In other words, let:

$x_1 \cdot p_1 + x_2 \cdot p_2 + \cdots + x_n \cdot p_n = y$

$\sum_{i=1}^n x_i = k$

Example:

$11 x_1 + 22 x_2 + 44 x_3 = 66$

$x_1+x_2+x_3 = 2$

would result in the solution: $x_1 = 0, x_2 = 1, x_3 = 1$.

I wonder if this has to be done by brute force with trying all possible combinations or if there are smarter algorithms for this kind of problem.

What kind of problem is this at all? Not being a mathematician i even don't know what to search for (and probably asked totally wrong - Sorry).

Please feel free to improve the question and add better tags.

  • 0
    Done.${}{}{}{}$2011-11-22

2 Answers 2

0

Per request of OP: it's a problem in diophantine equations, more specifically in systems of linear diophantine equations.

1

While this question may make more sense at math.SE, for what it is worth you should review the topic of linear algebra and in particular how to solve a system of linear equatiions.

Your system of equations may have one unique solution, may have no solution or multiple (infinite) solutions depending on the nature of the system. See the link above for more details.

The problem moves from the domain of math to statistics if you assume that $y$ is measured with error. In other words, instead of an exact decomposition of $y$ into its constituent components, you have something like the below:

$y = x_1 \cdot p_1 + x_2 \cdot p_2 + ... x_n \cdot p_n + \epsilon$

where $\epsilon$ is an error term that captures uncertainty in the measurement of $y$.

If your situation is such that uncertainty in $y$ needs to be taken into account (as the above) then you should start with a review of linear regression.

  • 1
    OP writes about "trying all possible combinations," which makes sense only if OP intends for all variables to be nonnegative integers. If that's the case, then we're not talking linear algebra, we're talking number theory (in particular, diophantine equations) and/or combinatorics.2011-11-21