Arduino.ru

Ну я же перебираю комбинацию ключей, а не размеров.

Если порядок вывода будет нарушен по сравнению с исходным массивом, надеюсь, это не будет ошибкой? Например так:

Ключи
2. 10-12: 514 руб. 55 коп.
6. 13-15: 628 руб. 45 коп.
7. 14-17: 702 руб. 76 коп.
9. 16-18: 819 руб. 89 коп.
12. 19-22: 1108 руб. 26 коп.
14. 6-8: 382 руб. 8 коп.
15. 9-11: 495 руб. 97 коп.
16. 24-27: 1715 руб. 70 коп.
Стоимость набора: 6367 руб. 66 коп.
Время расчёта: 319 миллисекунд

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

Та ладно, клиника это когда механик не умеет закручивать/откручивать гайки; электронщик паять; а программист программировать, врач лечить и так далее.

Ну я всё-таки за идею перебора сочетаний ключей без повторений с последующей проверкой на наличие всех размеров и сравнению стоимости полученных наборов.

От перебора так или иначе никуда не деться. Самый интересный вопрос - отсечение бесперспективных вариантов. Т.е. сокращение объема перебора.

Дополню для желающих погуглить такие приёмы: это называется "метод ветвей и границ".

Первый фундаментальный вопрос как обозначать наборы и желательно в цифрах, так как все же МК считает в цифрах. Допустим в условии даны 3 гаечных ключа. Сколько наборов из их можно собрать. Правильно 8 наборов. От набора когда ключей нет 000 , до того когда состоят из трех ключей 111. Думаю вам будет понятно. что позиция это номер ключа в задании а 1-испльзуется/0 -нет.  Дальше создается тип данных набор, стоимость набора, на сколько гаек он применим. И две функции определение стоимости по набору и определение количества гаек по набору.  Ну а дальше уже проявляйте навыки эффективного программирования.

ПС: Так как в условии дано 17 ключей, то на описания набора хватит 3-х байтов. всего вариантов набора будет 2^17=131072 включая когда все ключи в наборе отсутсвуют. Так что достаточно их перебрать сохранив тот вариант когда при большем количестве гаек будет меньшая цена.

Методом полного перебора.

Ключи
1. 6-8: 382 руб. 8 коп.
4. 9-11: 495 руб. 97 коп.
5. 10-12: 514 руб. 55 коп.
8. 13-15: 628 руб. 45 коп.
10. 14-17: 702 руб. 76 коп.
12. 16-18: 819 руб. 89 коп.
15. 19-22: 1108 руб. 26 коп.
17. 24-27: 1715 руб. 70 коп.
Стоимость набора: 6367 руб. 66 коп.
Время расчёта: 38582 миллисекунд

Буду думать как ускорить.

Начните с #57

Ключи
2. 10-12: 514 руб. 55 коп.
6. 13-15: 628 руб. 45 коп.
7. 14-17: 702 руб. 76 коп.
9. 16-18: 819 руб. 89 коп.
12. 19-22: 1108 руб. 26 коп.
14. 6-8: 382 руб. 8 коп.
15. 9-11: 495 руб. 97 коп.
16. 24-27: 1715 руб. 70 коп.
Стоимость набора: 6367 руб. 66 коп.
Время расчёта: 319 миллисекунд

Евгений Петрович, повторю вопрос. Если порядок вывода не принципиален, готов выложить свою версию.

Я думал это риторический вопрос. Порядок вывода в условии задачи не определён, так что делайте какой хотите. Выкладывайте, а я проверю на нескольких различных исходных наборах. Буду благодарен. если прокомментируете структуры исходных данных, чтобы мне меньше в ней разбираться.

//
//  Тип данных для хранения ключа
//
struct Spanner : public Printable {
  uint32_t price;// цена в копейках
  uint8_t size1;  // размер 1
  uint8_t size2;  // размер 2
  uint8_t included; // если 1, то включается в результирующий набор,0 - возможно будет включен,10 - исключен из перебора

  //ЗДЕСЬ НЕ ТАК,КАК У ВАС. included если 1 (оn), то включается в результирующий набор,0 (off) - возможно будет включен,10 (excluded) - исключен из перебора

  Spanner(const uint8_t s1, const uint8_t s2, const uint32_t p, const uint8_t ini = 0)
    :  price(p), size1(s1), size2(s2), included(ini) {}

  size_t printTo(Print & p) const {
    size_t res = p.print(size1);
    res += p.print('-');
    res += p.print(size2);
    res += p.print(": ");
    res += printPrice(p, price);
    return res;
  }

  static size_t printPrice(Print & p, const uint32_t priceCop) {
    size_t res = p.print(priceCop / 100);
    res += p.print(" руб. ");
    res += p.print(priceCop % 100);
    res += p.print(" коп.");
    return res;
  }
};



//
//  Массив всех ключей
//
static Spanner spanners[] = {
  {6, 8 , 38208},
  //{22, 24, 145560},
  {8, 9 , 41520},
  {8, 10, 43054},
  {9, 11, 49597},
  {14, 15, 61714},
  //{13, 12 , 30000},
 // {15, 17, 31000},
  {14, 17, 70276},
  {16, 17, 76496},
  {16, 18, 81989},
  {17, 19, 82312},
  {10, 12, 51455},
  {12, 13, 56544},
  {12, 14, 57675},
  {13, 15, 62845},
  {18, 19, 82877},
  {19, 22, 110826},
  {22, 24, 161570},
  {24, 27, 171570}

  /*{6, 8 , 38208},
    {9, 11, 49597},
    {8, 9 , 41520},
    {6, 8 , 39208},
    {24, 27, 171570},
    {8, 24, 1570},
    {24, 27, 201570}*/

};
static constexpr uint8_t totalSpanners = sizeof(spanners) / sizeof(spanners[0]);
const uint8_t on = 1, off = 0, excluded = 10;// если 1, то включается в результирующий набор,0 - возможно будет включен,10 - исключен из перебора

//
//  Эта функция вычисляет оптимальный набор ключей
//  и устанваливает поле included в on для ключей,
//  которые попадают в решение, и off или excluded для ключей,
//  которые не попадают в решение.
//
void doCalculations(void) {
  spanSort(spanners);              //отсортировали
  uint8_t quantityOff;            //ввели переменную кол-ва ключей, которые могут быть включены "off" в набор
  uint8_t quantityOn;            //ввели переменную кол-ва ключей, которые могут быть включены "off" в набор
  uint8_t quantitySize = totalSize();//кол-во уникальных размеров и заодно удалили (excluded) дубли
  uint8_t minQuantSpann;            //ввели переменную миним. кол-во ключей, из которых может состоять набор
  if (quantitySize % 2 == 0)
    minQuantSpann = quantitySize / 2;
  else minQuantSpann = quantitySize / 2 + 1; //Вычислили мин. возможное кол-во ключей
  //Serial.println(minQuantSpann);
  quantityOn = unique();                        //включили уникальные 6*8; 9*11; 24*27.
  exclud();                        //Тут исключать 8*9
  quantityOff = offSpanners();     //
  if (quantityOff == 0)return;
  sortOff(spanners); //Сортировка невклученных офф вперед
  //перебор вариантов.Почти все, что выше исключительно для умеьшения возм. сочетаний и времени.
  bruteForce(minQuantSpann, quantityOff, quantityOn, quantitySize);
}

//
//  Функция печатает результирующий
//  набор ключей и его стоимость
//
void printResults(void) {
  Serial.println("Ключи");
  uint32_t total = 0;
  for (uint8_t i = 0; i < totalSpanners; i++) {
    if (spanners[i].included == on) {
      Serial.print(i + 1);
      Serial.print(". ");
      Serial.println(spanners[i]);
      total += spanners[i].price;
    }
  }
  Serial.print("Стоимость набора: ");
  Spanner::printPrice(Serial, total);
  Serial.println();
}
//--------------------------------------------------


//
// Функция пнребора вариантов сочетаний ключей
//
void  bruteForce(uint8_t minQ, uint8_t qOff, uint8_t qOn, uint8_t qSize)
{
  uint8_t tempArr[qOff];
  uint32_t tempTotal = 0;
  //тут цикл, и не забывать про дин массивы память освобождать ретюрн выход из цикла
  for ( minQ; minQ <= qOff; minQ++)
  {                                                             //Serial.print(minQ);  Serial.print(' ');
    bool flagComplect = false;
    uint8_t *currArr;
    currArr = new uint8_t[minQ - qOn];
    uint32_t currTotal = 0;

    for (uint8_t i = 0; i < minQ - qOn; i++)                     //первое сочетание ключей
      currArr[i] = i + 1;
    for (uint8_t i = 0; i < minQ - qOn; i++)                     //сделали их "on"
      spanners[currArr[i] - 1].included = on;
    if ( totalSizeOn(qOff, qOn, qSize) == true)                  //если собрался правильный набор набор
    {
      for (uint8_t i = 0; i < qOff + qOn; i++)                   //подсчитали цену
      {
        if (spanners[i].included == on)
          currTotal += spanners[i].price;
      }
      if ( currTotal <= tempTotal || tempTotal == 0  )            //если цена  меньше записанной или это первый набор
      {
        tempTotal = currTotal;                                    //записываем цену
        for (uint8_t i = 0; i < qOff; i++)                        //темп аррей делаем пустым
          tempArr[i] = 0;
        for (uint8_t i = 0; i < minQ - qOn; i++)
        {
          tempArr[currArr[i] - 1] = 1;                            //записываем в темп аррей
          //Serial.print(currArr[i]);  Serial.print(' ');
        }
        flagComplect = true;                                      //поднимаем флаг "собран комплект"

      }
    }
    for (uint8_t i = 0; i < minQ - qOn; i++)                      //сбросили ключи в "off"
      spanners[currArr[i] - 1].included = off;

    while (NextSet(currArr, qOff, minQ - qOn))                     //новое сочетание ключей
    {

      for (uint8_t i = 0; i < minQ - qOn; i++)                     //сделали их "on"
      {
        spanners[currArr[i] - 1].included = on;
      }
      if ( totalSizeOn(qOff, qOn, qSize))                          //если собрался правильный набор набор
      {
        for (uint8_t i = 0; i < qOff + qOn; i++)                   //подсчитали цену
        {
          if (spanners[i].included == on)
            currTotal += spanners[i].price;
        }
        if ( currTotal <= tempTotal || tempTotal == 0  )            //если цена  меньше записанной или это первый набор
        {
          tempTotal = currTotal;                                   //записываем цену
          for (uint8_t i = 0; i < qOff; i++)                       //темп аррей делаем пустым
            tempArr[i] = 0;
          for (uint8_t i = 0; i < minQ - qOn; i++)
          {
            tempArr[currArr[i] - 1] = 1;                           //записываем в темп аррей
            //Serial.print(currArr[i]);  Serial.print(' ');
          }
          flagComplect = true;                                     //поднимаем флаг "собран комплект"
        }
      }

      for (uint8_t i = 0; i < minQ - qOn; i++)                     //сбросили ключи в "off"
        spanners[currArr[i] - 1].included = off;
      if ( flagComplect == true )                                  // Если комплект собрался
        break;                                                     //выходим из переборa (четное кол - во ключей - без вриантов;
                                                                   // нечетное - первым нйдет дешевый.
    }

    delete[] currArr;                                              // динамич. массив удаляем

    if (flagComplect == false)
    {
      for (uint8_t i = 0; i < qOff; i++)                           //если в иттерации не нашли комплект дешевле выходим
        spanners[i].included = tempArr[i];
      break;
    }

    if ( qOff == minQ )                                            //Последняя иттер.
    {
      for (uint8_t i = 0; i < qOff; i++)
        spanners[i].included = tempArr[i];
    }

  }
}
//-------------------------------------------------



//Функция вычисляет  количество существующих размеров среди включенных "On"ключей и сравнивает с зна
bool totalSizeOn(uint8_t qOff, uint8_t qOn, uint8_t qSize)
{
  uint8_t inSize = 0;
  for (uint8_t i = 0; i < qOn + qOff; i++)
  { bool flag1 = false;
    bool flag2 = false;
    if (spanners[i].included == on)

    {
      for (int k = i - 1; k >= 0; k--)
      { if (spanners[k].included != on)
        {
          continue;
        }
        if (spanners[i].size1 == spanners[k].size1 ||
            spanners[i].size1 == spanners[k].size2)
        {
          flag1 = true;
        }
        if (spanners[i].size2 == spanners[k].size1 ||
            spanners[i].size2 == spanners[k].size2)
        {
          flag2 = true;
        }
      }
      if (flag1 == false) inSize++;
      if (flag2 == false) inSize++;
    }
  }

  if (inSize != qSize)
    return false;
  else return true;
}
//---------------------------------------------------------



//
//Функция всех сочетаний для чисел 1…n по m.
//Честно содрана на <a href="https://prog-cpp.ru/combinations/" rel="nofollow">https://prog-cpp.ru/combinations/</a>
//
bool NextSet(uint8_t *a, uint8_t  n, uint8_t  m)
{
  uint8_t k = m;
  for (int i = k - 1; i >= 0; --i)
    if (a[i] < n - k + i + 1)
    {
      ++a[i];
      for (uint8_t j = i + 1; j < k; ++j)
        a[j] = a[j - 1] + 1;
      return true;
    }
  return false;
}
//-----------------------------------------------------

//
//Функция подсчета невключенных(off)ключей
//
uint8_t offSpanners()
{
  uint8_t j = 0;
  for (uint8_t i = 0; i < (totalSpanners ); i++)
  {
    if (spanners[i].included == off)
      j++;
  }
  return j;
}
//----------------------------------------

//
// функция сортировки ключей по "off"; ключи со значением included == off станут первыми
//
void sortOff(Spanner * spanarray)
{
  Spanner tmp[] = {};
  for (uint8_t i = 0; i < (totalSpanners ); i++)
  {
    for (int j = 0; j < totalSpanners - 1; j++)
    {
      if ((spanarray[j].included) > (spanarray[j + 1].included))
      {
        tmp[0] = spanarray[j];
        spanarray[j] = spanarray[j + 1];
        spanarray[j + 1] = tmp[0];
      }
    }
  }
}
//------------------------------------------------------

//
//Функция исключает из анализа (excluded) ключи, размеры которых дублируют обязательно включенные функцией unique()
//
//
void exclud()
{
  uint8_t inSp = 0;
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    if (spanners[i].included == on) inSp++;
  }
  inSp = inSp * 2;
  uint8_t *arrayTemp = new uint8_t[inSp];
  uint8_t j = 0;
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    if (spanners[i].included == on)
    {
      arrayTemp[j] = spanners[i].size1;
      j++;
      arrayTemp[j] = spanners[i].size2;
      j++;
    }
  }
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    bool flag1 = false;
    bool flag2 = false;
    if (spanners[i].included == off)
    {
      for (uint8_t k = 0; k < j; k++)
      {
        if (spanners[i].size1 == arrayTemp[k] )
        {
          flag1 = true;
        }
        if (spanners[i].size2 == arrayTemp[k])
        {
          flag2 = true;
        }
      }

    }
    if (flag1 == true && flag2 == true )
    {
      spanners[i].included = excluded;
    }
  }
  delete[] arrayTemp;
}
//-----------------------------------------------------------

//
// Функция определяет неповторяющиеся размеры и ключи, которым они принадлежат, "делаем" "on"
//
uint8_t unique()
{
  uint8_t uniqueSpanner = 0;
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    bool flag1 = false;
    bool flag2 = false;
    for (uint8_t k = 0; k < totalSpanners; k++)
    {
      if (i == k) continue;                              //сам на себя
      if (spanners[k].included == excluded) continue;     //на удаленный
      if (spanners[i].size1 == spanners[k].size1 ||
          spanners[i].size1 == spanners[k].size2)
      {
        flag1 = true;
      }
      if (spanners[i].size2 == spanners[k].size1 ||
          spanners[i].size2 == spanners[k].size2)
      {
        flag2 = true;
      }
    }
    if (flag1 == false || flag2 == false)
    {
      spanners[i].included = on;
      uniqueSpanner++;
    }
  }
  return uniqueSpanner;
}
//------------------------------------------

//
//Функция вычисляет общее количество существующих размеров и удаляет (excluded) дубли ключей
uint8_t totalSize()
{
  uint8_t inSize = 0;
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    bool flag1 = false;
    bool flag2 = false;
    for (int k = i - 1; k >= 0; k--)
    {
      if (spanners[i].size1 == spanners[k].size1 ||
          spanners[i].size1 == spanners[k].size2)
      {
        flag1 = true;
      }
      if (spanners[i].size2 == spanners[k].size1 ||
          spanners[i].size2 == spanners[k].size2)
      {
        flag2 = true;
      }
      if ((spanners[i].size1 == spanners[k].size1 ||
           spanners[i].size1 == spanners[k].size2) &&
          (spanners[i].size2 == spanners[k].size1 ||
           spanners[i].size2 == spanners[k].size2))

      {
        spanners[i].included = excluded;
      }
    }
    if (flag1 == false) inSize++;
    if (flag2 == false) inSize++;
  }
  return inSize;
}
//-------------------------------------------------------

//
// функция сортировки ключей от дешевых к дорогим
//
void spanSort(Spanner * spanarray)
{
  Spanner tmp[] = {};
  for (uint8_t i = 0; i < (totalSpanners ); i++)
  {
    for (int j = 0; j < totalSpanners - 1; j++)
    {
      if ((spanarray[j].price) > (spanarray[j + 1].price))
      {
        tmp[0] = spanarray[j];
        spanarray[j] = spanarray[j + 1];
        spanarray[j + 1] = tmp[0];
      }
    }
  }
}
//------------------------------------------------------
void setup(void) {
  Serial.begin(9600);
  const uint32_t start = millis();
  doCalculations();
  //uint8_t nota;
  //nota = totalSize();
  //Serial.print("notUnique "); Serial.print(nota); Serial.print('\n');
  const uint32_t duration = millis() - start;
  printResults();
  Serial.print("Время расчёта: ");
  Serial.print(duration);
  Serial.println(" миллисекунд");
}

void loop(void) {}

Стиль "Ма-ма мы-ла ра- му". Ну как умею.

P.S. Код изменил. 1-й раз залил неверную версию.

Набор и время еще укажите

Исходный набор:

    {6, 8 , 38208},
    {8, 9 , 41520},
    {8, 10, 43054},
    {9, 11, 49597},
    {10, 12, 51455},
    {12, 13, 56544},
    {12, 14, 57675},
    {13, 15, 62845},
    {14, 15, 61714},
    {14, 17, 70276},
    {16, 17, 76496},
    {16, 18, 81989},
    {17, 19, 82312},
    {18, 19, 82877},
    {19, 22, 110826},
    {22, 24, 145560},
    {24, 27, 171570}

Ключи
2. 10-12: 514 руб. 55 коп.
6. 13-15: 628 руб. 45 коп.
7. 14-17: 702 руб. 76 коп.
9. 16-18: 819 руб. 89 коп.
12. 19-22: 1108 руб. 26 коп.
14. 6-8: 382 руб. 8 коп.
15. 9-11: 495 руб. 97 коп.
16. 24-27: 1715 руб. 70 коп.
Стоимость набора: 6367 руб. 66 коп.
Время расчёта: 430 миллисекунд

Тот же набор, но ключ 13*15 можно заменить двумя дешевыми 13*12 и 15*17:

  {6, 8 , 38208},
  {8, 9 , 41520},
  {8, 10, 43054},
  {9, 11, 49597},
  {14, 15, 61714},
  {13, 12 , 30000},
  {15, 17, 31000},
  {14, 17, 70276},
  {16, 17, 76496},
  {16, 18, 81989},
  {17, 19, 82312},
  {10, 12, 51455},
  {12, 13, 56544},
  {12, 14, 57675},
  {13, 15, 62845},
  {18, 19, 82877},
  {19, 22, 110826},
  {22, 24, 161570},
  {24, 27, 171570}

Ключи
1. 13-12: 300 руб. 0 коп.
2. 15-17: 310 руб. 0 коп.
3. 8-10: 430 руб. 54 коп.
5. 12-14: 576 руб. 75 коп.
10. 16-18: 819 руб. 89 коп.
13. 19-22: 1108 руб. 26 коп.
15. 6-8: 382 руб. 8 коп.
16. 9-11: 495 руб. 97 коп.
17. 24-27: 1715 руб. 70 коп.
Стоимость набора: 6139 руб. 19 коп.
Время расчёта: 1015 миллисекунд

И еще один странный набор ключей с уникальными размерами и  более дорогими дубликатами:

    {6, 8 , 38208},
    {9, 11, 49597},
    {8, 9 , 41520},
    {6, 8 , 49200},
    {14, 15, 61714},
    {24, 27, 171570},
    {8, 24, 1570},
    {24, 27, 201570}

Ключи
2. 6-8: 382 руб. 8 коп.
5. 9-11: 495 руб. 97 коп.
6. 14-15: 617 руб. 14 коп.
7. 24-27: 1715 руб. 70 коп.
Стоимость набора: 3210 руб. 89 коп.
Время расчёта: 0 миллисекунд

kolyn - исходный набор ключей, если я понял - дан в условии Конкурса.

Откуда вы другие наборы взяли? Если придумали сами - зачем их публиковать в этой ветке?

Нет, там, наоборот, сказано:

Если бы Вы конкретнее изложили свою просьбу, а именно показать результат выполнения программы с набором ключей, заданных в условиях конкурса, я бы так и сделал;)

прошу прощения, значит недочитал :)

Тем не менее, для упрощения сравнения эффективности решений участников, лучше указывать время разбора одного единственного набора - приведенного в условиях

Упс, крыть нечем :)

Евгений Петрович, хотелось бы Вашей реакции. Зачтено? Нет?

Я пока ещё тесты не запускал, в выходные кода ещё не было, а сейчас тяжко, но я постараюсь, и как только, так сразу.

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

Есть и другое соображение - возможность "заточки" программы на конкретный набор, т.е. если программа "узнает" предпочтительный набор, он выдает заранее подготовленный вариант мгновенно, а на всех остальных наборах дает правильное, но неоптимальное (очень долгое) решение. По Вашему предложению именно такая программа должна стать победителем.

По моему мнению, программа, подводящая итоги, должна либо пытаться восстановить асимптотическую сложность на основе нескольких примеров, либо брать результаты самого "тяжелого" варианта (естественно того, который заранее не известен участникам).

то что вы описываете - это читерство :) и оно легко видно в исходном коде.

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

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

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

 ИМХО, без какого-то тестового набора или нескольких наборов нет четкого критерия первенства.

Например, среднее от Время/Ключ для N различных тестовых наборов.

Но это решать не мне;)

Согласаен.

Естественно. Но для чистоты эксперимента эти тестовые наборы не должны быть заранее известны разработчикам.

В математике есть три разных вида среднего. Не говоря даже о медиане, которая также претендует на это звание.

И, если Время/Ключ - это формула, то вряд ли она имеет верную размерность. Объем перебора - отнюдь не линейная функция от числа ключей.

А Вам какое больше нравится?;)

Да. Это формула. И она имеет правильную размерность. мс / шт = мс.

Главное не победа, а участие. :)

В своих ранее сделанных поделках я структуры и указатели не использовал. Плохо в них разбираюсь.

И максимальное "разумное" количество ключей для этого кода равно 64.

Результат для набора из задания:

Ключи
2. 19-22: 1108 руб. 26 коп.
5. 16-18: 819 руб. 89 коп.
7. 14-17: 702 руб. 76 коп.
8. 13-15: 628 руб. 45 коп.
12. 10-12: 514 руб. 55 коп.
15. 6-8: 382 руб. 8 коп.
16. 9-11: 495 руб. 97 коп.
17. 24-27: 1715 руб. 70 коп.
Стоимость набора: 6367 руб. 66 коп.
Время расчёта: 3529 миллисекунд

Код:

struct Spanner : public Printable {
  uint32_t price;// цена в копейках
  uint8_t size1;  // размер 1
  uint8_t size2;  // размер 2

  Spanner(const uint8_t s1, const uint8_t s2, const uint32_t p) 
    :  price(p), size1(s1), size2(s2) {}
  
  size_t printTo(Print & p) const {
    size_t res = p.print(size1);
    res += p.print('-');
    res += p.print(size2);
    res += p.print(": ");
    res += printPrice(p, price);
    return res;
  }
  
  static size_t printPrice(Print & p, const uint32_t priceCop) {
    size_t res = p.print(priceCop / 100);
    res += p.print(" руб. ");
    res += p.print(priceCop % 100);
    res += p.print(" коп.");
    return res;
  }
};

//  Массив всех ключей
static Spanner spanners[] = {
    {6, 8 , 38208},
    {8, 9 , 41520},
    {8, 10, 43054},
    {9, 11, 49597},
    {10, 12, 51455},
    {12, 13, 56544},
    {12, 14, 57675},
    {13, 15, 62845},
    {14, 15, 61714},
    {14, 17, 70276},
    {16, 17, 76496},
    {16, 18, 81989},
    {17, 19, 82312},
    {18, 19, 82877},
    {19, 22, 110826},
    {22, 24, 145560},
    {24, 27, 171570}
    
    
};
static constexpr uint8_t totalSpanners = sizeof(spanners) / sizeof(spanners[0]);

bool flag1=0, flag2=0, uSpanners[64];
uint8_t allSizes=0, n=0, sizes[128], cSizes[128], elem=0, noKeys=0, unique = 0; 
uint32_t rezTotal = 0, total0 = 0, total = 0;
uint64_t collection=0, rezCollection=0, p0, p=1;

// Функция которая выполняется первой и один раз.
void first(void) {
    memset(sizes, 0, sizeof(sizes[0])*128); // Обнуление массива размеров.
    memset(cSizes, 0, sizeof(cSizes[0])*128); // Обнуление массива кол-ва одинаковых размеров.
    memset(uSpanners, 1, sizeof(uSpanners[0])*64); // Установка единиц в массиве для вычисления ключей, которые полюбому попадают в набор.
    
    // Поиск всех размеров ключей и кол-ва каждого размера
    for (uint8_t i=0; i < totalSpanners; i++) {
      for (uint8_t j=0; j < allSizes; j++) {
        if (sizes[j] == spanners[i].size1) {flag1=1; cSizes[j]++;}
        if (sizes[j] == spanners[i].size2) {flag2=1; cSizes[j]++;}
      }
        if (!flag1) {sizes[allSizes] = spanners[i].size1; allSizes++;} else flag1=0; 
        if (!flag2) {sizes[allSizes] = spanners[i].size2; allSizes++;} else flag2=0;
    }
    n = round(((float)allSizes/2)); // половина всех размеров, для рассчёта границы по кол-ву ключей в наборе
    
    // Выявление ключей, которые полюбому будут в наборе (ключи у которых хотя бы один размер не повторяется с другими ключами), и вычисление их кол-ва.
    for (uint8_t j=0; j < allSizes; j++) 
      if (cSizes[j] == 0) {
        unique++;
        for (uint8_t i = 0; i < totalSpanners; i++) {
          if (spanners[i].size1 == sizes[j]) uSpanners[i] = 0;
          if (spanners[i].size2 == sizes[j]) uSpanners[i] = 0;
        }
    }

    // Сортировка массива структур, ключи, которые полюбому будут в наборе, перемещаются в конец массива
    Spanner tmp[] = {}; uint8_t temp = 0;
    for (uint8_t i = 0; i < totalSpanners; i++)
      for (uint8_t j = 0; j < totalSpanners - i - 1; j++)
      if ((uSpanners[j]) < (uSpanners[j + 1])) {
        temp = uSpanners[j];
        uSpanners[j] = uSpanners[j + 1];
        uSpanners[j + 1] = temp;
        tmp[0] = spanners[j];
        spanners[j] = spanners[j + 1];
        spanners[j + 1] = tmp[0];
      }
    
    // Сортировка массива структур по цене (от максимальной к минимальной) без ключей, которые полюбому будут в наборе.
    for (uint8_t i = 0; i < totalSpanners - unique; i++)
      for (uint8_t j = 0; j < totalSpanners - i - 1 - unique; j++)
      if ((spanners[j].price) < (spanners[j+1].price)) {
        tmp[0] = spanners[j];
        spanners[j] = spanners[j + 1];
        spanners[j + 1] = tmp[0];
      }    
}

// Функция отсечения неперспективных коомбинаций
bool calc(void) {
   flag1=0; flag2=0;  total=0; elem=0; p=1; noKeys=0;
    for (uint8_t i=0; i < totalSpanners; i++,p=p*2) {
       if (!bool((collection) & (p))){
        for (uint8_t j=0; j < elem; j++) {          
          if (sizes[j] == spanners[i].size1) flag1=1;
          if (sizes[j] == spanners[i].size2) flag2=1;
        }
        if (!flag1) {sizes[elem] = spanners[i].size1; elem++;} flag1=0; 
        if (!flag2) {sizes[elem] = spanners[i].size2; elem++;} flag2=0;      
        total = total + spanners[i].price; 
       } else {
        noKeys++;
        if (noKeys > totalSpanners - n) return 0; // Граница по кол-ву ключей в коомбинации
      }
      if ((total > rezTotal) && (rezTotal != 0)) return 0; // Граница по сумме цен ключей
   }
   if (elem != allSizes) return 0; // Отсечение коомбинаций в которых нет всех размеров
   return 1; 
}

void doCalculations(void) {
   // Вычисление верхней границы перебора.
   for (uint8_t i =0; i < totalSpanners-unique;i++) collection |= (1LL<<i);
   // Основной цикл перебора
   do{  
     collection--;
     if (calc()) if ((total < rezTotal) || (rezTotal == 0)) {rezTotal = total; rezCollection=collection;}
  }while (collection>1); 
}

void printResults(void) {
  Serial.println("Ключи");
  uint32_t total = 0; uint64_t r=1;
  for (uint8_t i = 0; i < totalSpanners; i++,r=2*r) {
    if (!bool((rezCollection) & (r))) {
      Serial.print(i + 1);
      Serial.print(". ");
      Serial.println(spanners[i]);
      total += spanners[i].price;
    }
  }
  Serial.print("Стоимость набора: ");
  Spanner::printPrice(Serial, total);
  Serial.println();
}

void setup(void) {
  Serial.begin(9600);
  const uint32_t start = millis();
  if (totalSpanners > 64) {Serial.println("Колличество ключей больше 64."); return;}
  first();
  doCalculations();
  const uint32_t duration = millis() - start;
  printResults();
  Serial.print("Время расчёта: ");
  Serial.print(duration);
  Serial.println(" миллисекунд");
}

void loop(void) {}  

Класс! Мужики, я так боялся, что не будет желающих!

Вот так и знал, что к слову "размерность" будут придирки.

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

Я не могу понять, в чем Вы видите ошибку!

Например в тесте 1  находим А ключей за время Т. Тогда на нахождение одного ключа Тср =  Т / А (мс). Проводим n РАЗЛИЧНЫХ тестов. Находим среднее (арифметическое напр.) : (Тср1 + Тср2 + ...+Тсрn)/n. Что не так?

ПС. Возможно в качестве "А" должно быть не кол-во найденных, а исходных ключей.

и не зря боялись, пришло другое поколение, сверх рационалистическое

" Они торчат под рейв и чем-то пудрят носы

они не такие, как мы." 

Бросьте. Это просто старческое брюзжание. Такие же, а может и лучше. Вспомните себя годков эдак в 25. Что бы вы предпочли - решать некую задачу, которая возможно и пощекочет ваш центр удовольствий в будущем или пойти с друзьями потусить прямо сейчас? Если первое - то у вас просто нет друзей. А те, кто ардуинит лет с 10 и не бросил это занятие, в 25 уж никак не "новичок".

В конкурсе примут участие только те, для кого программирование - хобби, кому не жалко на на это времени, у кого "базовые потребности" уже удовлетворены. Ради кайфа в тот момент, когда оно "заработало!!!".

кстати да, стоило бы четче сформулировать. для кого этот конкурс.  Потому как задачка, прямо скажем, далеко не для начального уровня. Те "новечки", что приходят сюда спрашивать, "как включить светодиод одним нажатием" - не смогут даже сформулировать подходы к решению, не говоря уж о написании работающего кода.

Поэтому актуален вопрос - кто они, участники этого конкурса? :)

Резюме)))

первое!

что значит друг? для меня это те, кому могу позвонить в любое время дня и ночи, сказать ты мне нужен и через 15 минут он будет у меня, и обратное естественно, таких немного...

PS ты попутал с приятелями, в русском это жеж просто - ПРИ Я Тело, разницу чувствуешь )))

Вы к этому осознанию прям со школьной скамьи пришли? Ну значит Вы мудрый человек! До меня это стало доходить после 30. Да и сейчас часто ошибаюсь в людях.  Но эт уже офтоп.

Ребята, не засоряйте тему

Профессионально программированием не занимался, только базовые курсы в школе (+факультатив) и в институте.

С ардуиной я начал знакомиться лет пять назад, всё началось с того, что я сделал гирлянду на новый год на конденсаторах и стартерах, но стартеры долго не прожили. Поэтому поставил под гирлянду нанку. Затем увлёкся идеей "Умного дома", у меня частный дом. Сейчас у меня действующая система из 3-х нанок, одной Меги и одного одноплатника с установленным на последнем MajorDoMo. В основном управление освещением, так же есть пара сигнализаций, пара гирлянд, цветной прожектор, датчики движения, температуры, влажности, давления, освещённости.

Поэтому программирование меня интересует как инструмент для этого моего увлечения.

Ну и да, мне ближе к сорока годикам. :)

kolyn,

попробуйте с вот таким набором данных

static Spanner spanners[] = {
	{1, 8 , 4},
	{2, 8 , 3},
	{4, 6 , 3},
	{12, 15 , 3},
	{2, 6 , 3},
	{4, 8 , 3},
	{6, 10 , 3}
};

У меня получилось

14:22:27.851 -> Ключи
14:22:27.851 -> 5. 12-15: 0 руб. 3 коп.
14:22:27.851 -> 6. 6-10: 0 руб. 3 коп.
14:22:27.851 -> 7. 1-8: 0 руб. 4 коп.
14:22:27.885 -> Стоимость набора: 0 руб. 10 коп.
14:22:27.885 -> Время расчёта: 0 миллисекунд

Здесь явно не хватает размеров 2 и 4.

AndreyD,

попробуйте с вот таким набором данных

static Spanner spanners[] = {
	{1, 2 , 1},
	{3, 4 , 1},
	{5, 6 , 1}
};

У меня получилось бесконечное исполнение. Может, и конечное, но больше 15 минут я уж не стал ждать.

static Spanner spanners[] = {
	{1, 8 , 4},
	{2, 8 , 3},
	{4, 6 , 3},
	{12, 15 , 3},
	{2, 6 , 3},
	{4, 8 , 3},
	{6, 10 , 3}
};

14:22:27.851 -> Ключи
14:22:27.851 -> 5. 12-15: 0 руб. 3 коп.
14:22:27.851 -> 6. 6-10: 0 руб. 3 коп.
14:22:27.851 -> 7. 1-8: 0 руб. 4 коп.
14:22:27.885 -> Стоимость набора: 0 руб. 10 коп.
14:22:27.885 -> Время расчёта: 0 миллисекунд

Упс. Ошибка в логике программы. Она основана на сортировке от дешевых к дорогим,а равенство цен я не учел(

Стоит исправлять или уже все?

Конечно, стоит.

Про другие ошибки рассказать? Ну, про то, что глаза сразу бросилось?

В этом Вы явно ошибаетесь.

Конечно!

Вы регулярно используете конструкцию

Spanner tmp[] = {};
...
tmp[0] = spanarray[j];

Видимо, Вы считаете, что в строке №1 выделили память и в строке №3 спокойно в неё пишете. Боюсь Вас разочаровать. Напечатайте в сериал sizeof Вашего tmp и посмотрите, сколько там выделилось.

Вы пишете в произвольную память. Если она не под что не распределена, Вам повезло - будет работать, а если она подо что-то выделена, Вы это что-то испортите. Полюбуйтесь, что бывает, когда так пишешь.

Если уж Вам там нужен массив, так пишите его размер явно или нормальный инициализатор.

Я в свою очередь думаю, что у Вас претензии к  (Тср1 + Тср2 + ...+Тсрn)/n просто к как к абстракной формуле. Вот и беседуем - Вы о круглом, я о красном;)

Именно. Это утверждение непосредственно следует из предложенной Вами формулы.

А она есть!

Видите ли, математика - это не просто набор значков. Каждая строка имеет свой смысл. Вот смысл в приведенной выше формуле есть только в том случае, если зависимость времени и количества линейна. В противном случае эту формулу применять нельзя.

PS. Если Вы вправду считаете, что все формулы равнозначны, будете ли Вы считать закон Ома по формуле U=I/R ? Чем она хуже U=I*R ?

Не бывает "абстрактных формул". Каждая из них имеет (либо не имеет) какой-то смысл.

Можно еще попробовать на таком простеньком наборе:

сорри, глюк