Резисторы

[The_Great_Satan]

Радиолюбитель Петя решил собрать детекторный приемник. Ему понадобился резистор с сопротивлением R Ом. В распоряжении Пети есть набор из n резисторов, сопротивления которых равны r1, r2, ... , rn Ом соответственно. Петя помнит, как вычисляется сопротивление последовательного соединений двух резисторов Rnew = R1 + R2 и параллельного соединения двух резисторов Rnew = (R1 * R2) / (R1 + R2). Петя хочет спаять некоторую последовательно-параллельную схему из имеющегося набора резисторов такую, что ее сопротивление ближе всего к R Ом (то есть абсолютная величина разности значений должна быть минимальна).
Напомним, что схема, составленная из одного резистора, -- последовательно-параллельная схема. Любая схема, полученная последовательным соединением двух последовательно-параллельных схем, -- последовательно-параллельная, также любая схема, полученная параллельным соединением двух последовательно-параллельных схем, -- последовательно-параллельная.
Разумеется, Петя не обязан использовать для изготовления схемы все имеющиеся резисторы.

Входные данные
В первой строке входного файла заданы числа n, R (1 <= n <= 7; 10 <= R <= 3000). Число R - вещественное, заданное не более чем с 4 знаками после запятой. Во второй строке содержится последовательность сопротивлений имеющихся в наличии резисторов r1, r2, ... , rn. Значения всех сопротивлений могут быть вещественными числами от 10 до 3000.

Выходные данные
В выходной файл необходимо вывести сопротивление такой схемы, сопротивление которой меньше всего отличается от R. Сопротивление выведите не менее чем с 6 знаками после десятичной точки.

Пример

Ввод
3 1.66
1 2 1

Вывод
1.666666666666666

#include "stdafx.h"
#include <iostream>
#include <cmath>
using namespace std;

double b[20],a[20];
int n,k;
double rx,r0,result=1e20;

void brute (double r,int pos) //процедура рекурсивного перебора
{
   if (pos==k) 
   {
      if (fabs(r0-r)<result) {result=fabs(r0-r);rx=r;}
    }
   else
   {   
      brute(r+a[pos],pos+1);

      brute(r*a[pos]/(a[pos]+r),pos+1);
   }
}

int main()
{
   cin>>n>>r0;

   for (int i=0;i<n;i++) cin>>b[i];

   for (int i=0;i<(1<<n);i++)
   {
      for(k=0;k<n;k++) a[k]=0;

      k=0;

      for (int j=0;j<n;j++)
      {
         if ((i & (1<<j))!=0) {a[k]=b[j];k++;} //выбираю из заданного набора некоторое подмножество
      }

      if (k!=0) 
      {
         brute(a[0],1); //пробегаю по подмножеству и ищу сопротивление, наиболее близкое к заданному
      }
   }
   
   cout.precision (10);
   
   cout<<fixed<<rx<<endl;
   
   return 0;
}

Программа перебирает далеко не все возможные варианты соединения резисторов, поэтому вопрос: как лучше переделать программу, чтобы она полноценно работала?

[The_Great_Satan]

Слышал, что можно сделать следующим образом: ищем все подмножества для набора резисторов, потом делаем разбиение каждого подмножества еще на 2 не пересекающихся. Но вот что дальше делать не понял, есть идеи, господа?

[Cave]

В порядке увеличения числа резисторов в подмножестве проходим по ним и записываем все возможные сопротивления, которые из них можно получить. Чтобы не плодить одни и те же результаты, нужно или ввести структуру данных типа дерева поиска, или сперва всё записывать в массив, потом его сортировать и потом удалять дубликаты (при этом в силу погрешностей при работе с числами с плавающей запятой сравнивать нужно не на равенство, а, например, на то, что модуль разности не более $10^{-10}$).

[The_Great_Satan]

Cave в сообщении #289242 писал(а):

Записываем все возможные сопротивления, которые из них можно получить.

А как считать эти самые всевозможные сопротивления? Для 7 резисторов, например, существует большое количество всевозможных комбинаций, как рассмотреть их все?

[Cave]

Вы же сами написали: перебрать всевозможные разбиения на два непересекающихся подмножества. Для каждого из них ответ посчитан. Все варианты для них нужно соединить поочерёдно последовательно и параллельно.
Сложность алгоритма с ходу не скажу, тут непросто подсчитать число различных вариантов для каждого подмножества.

[The_Great_Satan]

Cave в сообщении #289365 писал(а):

Вы же сами написали: перебрать всевозможные разбиения на два непересекающихся подмножества.

Проблема была с реализацией этого разбиения, но она уже решена.
Спасибо всем отписавшимся.