Построение дробей Задача на собеседовании

Недавно я наткнулся на следующий вопрос из интервью, мне было интересно, будет ли работать подход динамического программирования, или/и есть ли какое-то математическое понимание, которое облегчило бы решение... Это очень похоже на то, как создаются двойники ieee754..

Вопрос: Имеется вектор V из N двойных значений. Где значение по i-му индексу вектора равно 1/2^ (i+1 ). например :1/2, 1/4, 1/8, 1/16 и т. д.

Вы должны написать функцию, которая принимает на вход одно двойное 'r', где 0 < r < 1, и вывести индексы V на стандартный вывод, что при суммировании даст значение, наиболее близкое к значению 'r', чем любая другая комбинация индексов из вектора V.

Кроме того, количество индексов должно быть минимальным, и в случае есть два решения, предпочтение следует отдать решению, ближайшему к нулю.

void getIndexes(std::vector<double>& V, double r)
{
.... 
}

int main()
{
   std::vector<double> V;
   // populate V...
   double r = 0.3;
   getIndexes(V,r);
   return 0;
}

Примечание.:Кажется, есть несколько SO'ers, которые не в настроении читать вопрос полностью. Итак, давайте все отметим следующее:

1. Решение, также известное как сумма, может быть больше, чем r -следовательно, любая стратегия постепенного вычитания дробей из r до тех пор, пока оно не достигнет нуля или около нуля, неверна

2. Существуют примеры r, где будет 2 решения, то есть |r -s0| == |r -s1| и s0 < s1 -, в этом случае следует выбрать s0, это немного усложняет задачу, поскольку решения в стиле ранца сначала имеют тенденцию к жадному завышению оценок.

3. Если вы считаете, что эта проблема тривиальна, вы, скорее всего, не поняли ее. Поэтому было бы неплохо прочитать вопрос еще раз.

РЕДАКТИРОВАТЬ (Матье М.):2 примера дляV = {1/2, 1/4, 1/8, 1/16, 1/32}

• r = 0.3,S = {1, 3}
• r = 0.256652,S = {1}