Sum of positive integers estimating sum of fractions

117 Views Asked by At

Given $m$ fractions adding up to an positive integer $n$

For example: $m=3\\n=10=\frac{30}{6}+\frac{20}{6}+\frac{10}{6}$

How can we find $m$ positive integers that sum to $n$ (a partition of $n$), that best estimate the fractions as a whole?

In this case the answer is clearly $z_1=3,\space z_2=5,\space z_3=2$

By "best estimate as a whole" I mean $\min \sum_{i=1}^N|\frac{p_i}{q_i}-n_i|$ , as user mvw pointed out.

1

There are 1 best solutions below

0
On BEST ANSWER

As a starting point, I would use a greedy algorithm. Initialize the m partition values to be close the individual fractional values. So in your example, the values (5,3,2) are naturally selected because they are each respectively the closest approximations to their fractional values.

After having done this selection, you may find that you are off by some error value z. The absolute value of z will necessarily be a whole number less than m. The trick then is to switch z values by either increasing or decreasing by 1, according to the direction you need to go. The trick then is to supply a greedy selection process for making the switch. Without loss of generality, I am going to assume that your total result underestimates the target. (The process is similar if you overestimate the target).

Since you are off by z and each initial estimate cannot be off by more than 1, there are at least z partition elements that are lower than the associated fraction. Consider only those elements where the estimate value is less than the fraction, and order these elements according to their error value. The trick now is to select the z elements with the largest error-values. (If there are ties for the largest error-values, select the elements arbitrarily between tied values). Having selected your largest error-values, you will add 1 to each of the estimate values. The error will naturally increase, but it should be the smallest possible increase possible.