title: Constructing fractions Interview challenge
body: <p>I recently came across the following interview question, I was wondering if a dynamic programming approach would work, or/and if there was some kind of mathematical insight that would make the solution easier... Its very similar to how ieee754 doubles are constructed.</p>
  
  <p><strong>Question:</strong>
  There is vector V of N double values. Where the value at the ith index of the vector is equal to 1/2^(i+1). eg: 1/2, 1/4, 1/8, 1/16 etc...</p>
  
  <p>You're to write a function that takes one double 'r' as input, where 0 &lt; r &lt; 1, and output the indexes of V to stdout that when summed will give a value closest to the value 'r' than any other combination of indexes from the vector V. </p>
  
  <p>Furthermore the number of indexes should be a minimum, and in the event there are two solutions, the solution closest to zero should be preferred.</p>
  
  <pre><code>void getIndexes(std::vector&lt;double&gt;&amp; V, double r)
  {
   .... 
  }
  
  int main()
  {
     std::vector&lt;double&gt; V;
     // populate V...
     double r = 0.3;
     getIndexes(V,r);
     return 0;
  }
  </code></pre>
  
  <p><strong>Note:</strong> It seems like there are a few SO'ers that aren't in the mood of reading the question completely. So lets all note the following:</p>
  
  <ol>
  <li><p>The solution, aka the sum may be larger than r - hence any strategy incrementally subtracting fractions from r, until it hits zero or near zero is wrong</p></li>
  <li><p>There are examples of r, where there will be 2 solutions, that is |r-s0| == |r-s1| and s0 &lt; s1 - in this case s0 should be selected, this makes the problem slightly more difficult, as the knapsack style solutions tend to greedy overestimates first.</p></li>
  <li><p>If you believe this problem is trivial, you most likely haven't understood it. Hence it would be a good idea to read the question again.</p></li>
  </ol>
  
  <p><strong>EDIT (Matthieu M.):</strong> 2 examples for <code>V = {1/2, 1/4, 1/8, 1/16, 1/32}</code></p>
  
  <ul>
  <li><code>r = 0.3</code>, <code>S = {1, 3}</code></li>
  <li><code>r = 0.256652</code>, <code>S = {1}</code></li>
  </ul>