An algorithm to deduce the terms of a weighted sum of integers?

Question

Given $n$ real positive base values $v_i$ and $n$ non-negative integer counts $c_i$, the weighted sum $V$ of base values is $$V = \sum_{i=1}^n c_iv_i$$ and the sum $C$ of counts is $$C = \sum_{i=1}^n c_i$$

Problem 1: Suppose that I'm given the weighted sum $V > 0$ and the sum of counts $C > 0$ and all base values $v_i$, but not the individual counts $c_i$. How can I recover the $c_i$?

A solution does not always exist, so let's allow some leeway.

Problem 2: Suppose that the given $C$ and $v_i$ are exact, but the given $V$ may be a bit off. Which $c_i$ give the best fit (for a suitable definition of "best" -- for example, which $c_i$ give a weighted sum closest to the given $V$)?

There is always a solution to problem 2, and there may be multiple solutions. If there are solutions to problem 2 that reproduce the given $V$ exactly, then those are solutions to problem 1, too.

---

If $n = 1$, then the solution to problem 2 is trivial: $c_1 = C$.

If $n = 2$, then the solution to problem 2 is still easy to find:

\begin{eqnarray} c_2 & = & C - c_1 \\ V & = & c_1 v_1 + (C - c_1) v_2 = C v_2 + (v_1 - v_2) c_1 \\ c_1 & = & \left[\frac{V - C v_2}{v_1 - v_2}\right] \end{eqnarray} where $[\cdot]$ stands for rounding to the nearest integer value.

If $n > 2$, then what is a good algorithm for solving this problem?

---

Here is a simple example of an application of this problem: I have 7 coins in my pocket. The possible denominations of the coins are 1 cent, 5 cents, 10 cents, and 25 cents. The total value of all coins combined is 49 cents. How many coins of each denomination do I have?

Trial and error shows that this particular puzzle has exactly one solution: 1 × 25 cents + 2 × 10 cents + 0 × 5 cents + 4 × 1 cent.

If the total value is 51 cents, then there are 2 solutions. If the total is 54 cents, then there is no exact solution to problem 1, but problem 2 has 4 solutions that are each only 1 cent off.

If none of the base values $v_i$ are pairwise coprime, then I expect that problem 2 always has exactly one solution.

EDIT: Solutions to the somewhat similar equation $$0 = \sum_{i=1}^n c_iv_i$$ with unknown integer $c_i$ and known real $v_i$ can be found using an integer relation algorithm. Could an adaptation of such an algorithm be used to solve my problem?

EDIT 2: We get some way towards a solution as follows: Define matrix $M$: $$ M = \begin{pmatrix} v_1 & v_2 & ... \\ 1 & 1 & ... \end{pmatrix} $$ and vector $\vec{b}$: $$ \vec{b} = \begin{pmatrix} V \\ C \end{pmatrix} $$ Then problem 1 may be restated as: Find $\vec{c}$ such that $$M\vec{c} = \vec{b}$$ and all $c_i$ are non-negative integers.

If the restriction on the values of $c_i$ is removed, then the solutions are $$\vec{c} = \vec{c}_\text{spec} + \vec{n} \qquad \text{(Eq. 1)}$$ where $\vec{c}_\text{spec}$ is a single specific solution and $\vec{n}$ is any vector that is part of the kernel of $M$ (i.e., that solves $M\vec{n} = \vec{0}$). We can find $\vec{c}_\text{spec}$ by choosing $c_i = 0$ for $i > 2$. That effectively reduces the problem to the $n = 2$ case discussed above and yields $$\vec{c}_\text{spec} = \begin{pmatrix} \dfrac{C v_2 - V}{v_2 - v_1} \\ \dfrac{V - C v_1}{v_2 - v_1} \\ 0 \\ \vdots \end{pmatrix}$$ A basis for the kernel can be found by Gaussian elimination or using Singular Value Decomposition. All solutions (if any) to problem 1 satisfy Eq. 1 and in addition have all $c_i$ be non-negative integers. So then the problem becomes: How do I find all integer-only $\vec{c}$ in the output of Eq. 1?

Answer 1

Hint:

You can picture the case of $n=2$ in 3D (axis $c_0,c_1,v$), by representing the weighted sum as a plane, which is intersected by the horizontal plane $v=V$. This intersection projects to a line on the plane $c_0,c_1$.

The allowed combinations are points on a unit square grid, such that $c_0+c_1=C$, i.e. aligned on a straight line. The solution or closest solution is given by the intersection of these two lines. (In the first quadrant.)

Now for $n=3$, the allowed configurations are the grid points on the plane $c_0+c_1+c_2=C$, which is intersected by a plane, giving a straight line. The solutions are the grid points closest to this line. (In the first octant.)

For larger $n$, you will need to find the grid points closest to an $n-1$-dimensional hyperplane.

If I am right, there is no better way than trying exhaustively the points close to the intersection space, the number of which grows exponentially with $n$.

Answer 2

Your problem can be formulated as integer linear program (ILP): $$ \max \{ 0_n^\top c \mid Ac = b, c \ge 0, c \in \mathbb{Z}^n \} $$ where $$ 0_n^\top = (0, \dotsc, 0) \in \mathbb{F}^n \\ A = (v, 1_n)^\top \in \mathbb{F}^{2\times n} \\ b = (V, C)^\top \in \mathbb{F}^2 $$ for some field $\mathbb{F}$, so you could use a solver like lpsolve for a particular problem intance.

The cost vector is the null vector, to turn all feasible points (those points that fulfill the constraints) into solutions.

If you are interested in solution algorithms you should read a book on integer programming, e.g. M. Conforti, G. Cornuéjols, G. Zambelli: Integer Programming, Springer.

Example:

Here is a simple example of an application of this problem: I have $7$ coins in my pocket. The possible denominations of the coins are $1$ cent, $5$ cents, $10$ cents, and $25$ cents. The total value of all coins combined is $4$9 cents. How many coins of each denomination do I have?

This example uses the R language. If not done already, install lpSolve:

> install.packages("lpSolve")
> install.packages("lpSolveAPI")

Load the library:

> library(lpSolveAPI)

Create a new model in $4$ unknowns and store it in the variable lprec:

> lprec<-make.lp(0,4)

Set the objective function to zero:

> set.objfn(lprec, c(0,0,0,0))

Now add the constraints, thus the rows of $A c = b$:

> add.constraint(lprec, c(1,5,10,25), "=", 49)
> add.constraint(lprec, c(1,1,1,1), "=", 7)

We set the types of the unknowns to integers:

> set.type(lprec,1, "integer")
> set.type(lprec,2, "integer")
> set.type(lprec,3, "integer")
> set.type(lprec,4, "integer")

Checking:

> lprec
Model name: 
           C1   C2   C3   C4       
Minimize    0    0    0    0       
R1          1    5   10   25  =  49
R2          1    1    1    1  =   7
Kind      Std  Std  Std  Std       
Type      Int  Int  Int  Int       
Upper     Inf  Inf  Inf  Inf       
Lower       0    0    0    0       

Now we ask lpsolve to solve

> solve(lprec)
[1] 0

And the objective function value is:

> get.objective(lprec)
[1] 0

As it should be. And now the solutions:

> get.variables(lprec)
[1] 4 0 2 1

Trial and error shows that this particular puzzle has exactly one solution: $1$ × $25$ cents + $2$ × $10$ cents + $0$ × $5$ cents + $4$ × $1$ cent.

This agrees with your solution.

If the total value is $51$ cents, then there are $2$ solutions. If the total is $54$ cents, then there is no exact solution to problem $1$, but problem $2$ has $4$ solutions that are each only $1$ cent off.

> get.variables(lprec)
[1] 1 5 0 1

This is one solution. To get all one would need to dig a bit deeper into R, see here.