Arduino.ru

LTO - enable:
 

Ключи
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 коп.
Время расчёта: 641 миллисекунд

LTO - disable:
 

Ключи
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 коп.
Время расчёта: 642 миллисекунд

Ну, вот, тоже мне LTO - даже скидку не организовал :-(

Ключи
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 коп.
Время расчёта: 3763 миллисекунд

Код:

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 uSpanners[64], dSpanners[64];
uint8_t sizes[128], cSizes[128], allSizes=0, n=0, unique=0, dbl=0, totalSpanners1=0, nKeys=0; 
uint64_t rezCollection=0;

// Функция которая выполняется первой и один раз.
void first(void) {
    bool flag1=0, flag2=0; uint8_t elem=0; uint32_t total = 0;

    memset(sizes, 0, sizeof(sizes[0])*128); // Обнуление массива размеров.
    memset(cSizes, 0, sizeof(cSizes[0])*128); // Обнуление массива кол-ва одинаковых размеров.
    memset(uSpanners, 1, sizeof(uSpanners[0])*64); // Установка единиц в массиве для вычисления ключей, которые полюбому попадают в набор.
    memset(dSpanners, 1, sizeof(dSpanners[0])*64); // Установка единиц в массиве для вычисления ключей, которые полюбому попадают в набор.
    
    // Поиск более дорогих дублей, всех размеров ключей и кол-ва каждого размера
    for (uint8_t i=0; i < totalSpanners; i++) {
      for (uint8_t j=0; j < totalSpanners; j++) 
        if (dSpanners[i] && i != j)
          if ((((spanners[i].size1 == spanners[j].size1) && (spanners[i].size2 == spanners[j].size2)) || 
              ((spanners[i].size1 == spanners[j].size2) && (spanners[i].size2 == spanners[j].size1))) &&
              (spanners[i].price <= spanners[j].price)) dSpanners[j] = 0; 

      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)); // половина всех размеров, для рассчёта границы по кол-ву ключей в наборе

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

    // Вычисление кол-ва дублей с большей ценой
    for (uint8_t i=0; i < totalSpanners; i++) 
      if (!dSpanners[i]) {dbl = totalSpanners - i; break;}

    totalSpanners1 = totalSpanners - dbl; // Кол-во ключей без дублей
    nKeys = totalSpanners - n - dbl;

    // Выявление ключей, которые полюбому будут в наборе (ключи у которых хотя бы один размер не повторяется с другими ключами), и вычисление их кол-ва.
    for (uint8_t j=0; j < allSizes; j++) 
      if (cSizes[j] == 0) {
        unique++;
        for (uint8_t i = 0; i < totalSpanners - dbl; i++) {
          if (spanners[i].size1 == sizes[j]) uSpanners[i] = 0;
          if (spanners[i].size2 == sizes[j]) uSpanners[i] = 0;
        }
    }

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

// Функция отсечения неперспективных коомбинаций
uint32_t calc(uint64_t collection, uint32_t rezTotal) {
   bool stopElem=0, flag2=0, flag1=0; uint8_t noKeys=0, elem=0; uint32_t total=0; uint64_t p=1; 

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

void doCalculations(void) {
   uint64_t collection=0; uint32_t total = 0, rezTotal=0;
   // Вычисление верхней границы перебора.
   for (uint8_t i = n; i < totalSpanners - unique - dbl;i++) collection |= (1ULL<<i);

   // Основной цикл перебора
   do{  
     if (collection != 0) collection--;
     total = calc(collection, rezTotal);
     if ((total != 0) || (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 - dbl; i++,r=r*2ULL) {
    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) {}  

Все, сдаюсь, прошу помощи...

У меня время расчета в этой задаче 516 миллисекунд, у ua6em и AndreyD 641.

Что сделал: 1. Проверил на другой ардуине, про мини - результат тот же. 2.Построчно вычитал код, не нашел никаких ляпов, вроде за границы массивов не вылезаю. 3.Понатыкал в разные места кода случайных переменных, инициализировал их значениями, организовал вывод в сериал - ни одна не испортилась. 4. В цикле перебора сделал вывод в сериал текущего миллис - все ровно, без скачков.

Выводы: ардуины исправны, память не порчу(99.9%). Фьюзы-шмузы и прочие загрузчики ни при чем - вывод в сериал работает, миллис тикает верно. Различие только в версиях ИДЕ - у меня 1.8.7, у товарищей поновее. 

Обновился до 1.8.13. Упс. Время расчёта: 641 миллисекунд против 516 в 1.8.7. Разница в 20%!!! Такое разве может быть и если да, то почему? Разные версии компиляторов создают разный код? В одном случае некие переменные хранит в ОЗУ, а в другом - держит их в регистрах, доступ к которым быстрее или как???

в 1.8.3 -

Ключи
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 коп.
Время расчёта: 642 миллисекунд

в 1.8.7
Ключи
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 коп.
Время расчёта: 642 миллисекунд
 

Видимо в 1.8.7 ты что-то правил

Нет. я этого не умею). Единственное, установлена Атмел Студио 7.0 и она ассоциирована с этой версией Ардуино. Может она поковырялась...

Увеличил возможное количество ключей в стартовом наборе до 100, если из них 36 и более дубли. На больше количество ключей уже памяти нанки перестаёт хватать.

А так продолжаю дорабатывать код.

Результат за выходные.

Ключи
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 коп.
Время расчёта: 3778 миллисекунд

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

  Spanner(const uint8_t s1, const uint8_t s2, const uint32_t p, const bool ini = true) 
    :  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;
  }
};

//  Массив всех ключей
// Ключей в массиве не больше 100
// Размеры от 1 до 155
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]);

uint8_t totalSpanners2=0, sizes[155], cSizes[155];  
uint64_t rezCollection=0;

void doCalculations(void) {
   bool stopElem=0, flag1=0, flag2=0, flag3=1; 
   uint8_t noKeys=0, elem=0, allSizes=0, n=0, unique=0, dbl=0, totalSpanners1=0, nKeys=0; 
   uint32_t iTotal=0, rezTotal=UINT32_MAX; 
   uint64_t collection=0;

    memset(sizes, 0, sizeof(sizes[0])*155); // Обнуление массива размеров.
    memset(cSizes, 0, sizeof(cSizes[0])*155); // Обнуление массива кол-ва одинаковых размеров.
   
    // Поиск более дорогих дублей, всех размеров ключей и кол-ва каждого размера
    for (uint8_t i=0; i < totalSpanners; i++) {
      for (uint8_t j=0; j < totalSpanners; j++) 
        if (spanners[i].included && i != j)
          if ((((spanners[i].size1 == spanners[j].size1) && (spanners[i].size2 == spanners[j].size2)) || 
              ((spanners[i].size1 == spanners[j].size2) && (spanners[i].size2 == spanners[j].size1))) &&
              (spanners[i].price <= spanners[j].price)) spanners[j].included = 0; 

      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)); // половина всех размеров, для рассчёта границы по кол-ву ключей в наборе

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

    // Вычисление кол-ва дублей с большей ценой
    for (uint8_t i=0; i < totalSpanners; i++) 
      if (!spanners[i].included) {dbl = totalSpanners - i; break;}

    totalSpanners1 = totalSpanners - dbl; // Кол-во ключей без дублей
    if (totalSpanners1 > 64) {Serial.println("Переполнен буфер перебора. Уменьшите колличество ключей."); return;}
    totalSpanners2 = totalSpanners1;
    nKeys = totalSpanners - n - dbl;

    // Выявление ключей, которые полюбому будут в наборе (ключи у которых хотя бы один размер не повторяется с другими ключами), и вычисление их кол-ва.
    for (uint8_t j=0; j < allSizes; j++) 
      if (cSizes[j] == 0) {
        unique++;
        for (uint8_t i = 0; i < totalSpanners - dbl; i++) {
          if (spanners[i].size1 == sizes[j]) spanners[i].included = 0;
          if (spanners[i].size2 == sizes[j]) spanners[i].included = 0;
        }
    }

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

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


  
   // Вычисление верхней границы перебора.
   for (uint8_t i = 0; i < totalSpanners1 - unique;i++) collection |= (1ULL<<i);
   // Основной цикл перебора
   do{  
     elem=0; noKeys=0; stopElem=0; iTotal=0; 
     if (collection != 0) collection--;
   
     for (uint8_t i=0; i < totalSpanners1; i++) 
       if (collection & (1ULL<<i)){
         // Граница по кол-ву ключей в наборе
         noKeys++;
         if (noKeys > nKeys) {if (stopElem) stopElem=0; break;}   
       } else {
         // Граница по сумме цен ключей
         iTotal = iTotal + spanners[i].price; 
         if (iTotal >= rezTotal) {if (stopElem) stopElem=0; break;}
        
         // Проверка наличия всех размеров
         if (!stopElem) {
           for (uint8_t j=0; j < elem; j++) {          
             if ((sizes[j] == spanners[i].size1) && !flag1) {flag1=1; if (flag2) break;}
             if ((sizes[j] == spanners[i].size2) && !flag2) {flag2=1; if (flag1) break;}
           }
           if (!flag1) {sizes[elem] = spanners[i].size1; elem++;} else flag1=0; 
           if (!flag2) {sizes[elem] = spanners[i].size2; elem++;} else flag2=0;      
           if (elem == allSizes) stopElem=1;
         }
         
       }
     
     // Если есть все размеры и не было отсечения по границам записываем сумму и набор
     if (stopElem) {rezTotal = iTotal; rezCollection=collection;}
   }while (collection > 0);  

}

void printResults(void) {
  Serial.println("Ключи");
  uint32_t total = 0;
  for (uint8_t i = 0; i < totalSpanners2; i++) {
    if (!((rezCollection) & (1ULL<<i))) {
      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 > 100) {Serial.println("Колличество ключей больше 100. Уменьшите их колличество."); return;}
  doCalculations();
  const uint32_t duration = millis() - start;
  printResults();
  Serial.print("Время расчёта: ");
  Serial.print(duration);
  Serial.println(" миллисекунд");
}

void loop(void) {}  

Отвлеченный вопрос. Есть ли на форуме отдельная тема про программирование "умных" домов на ардуино? Как единое целое, а не отдельно по компонентам.

Правильно я мыслю, что по этому вопросу надо смотреть в сторону Событийно-ориентированного программирования и ООП?

Нету. Если дом умный, то чо его программировать, он и сам всё знает. 

Не так выразился. Имел ввиду использование ардуино как узлов "умного" дома. Хотя один годик у меня всё полностью было на ардуинах, в качестве сервера использовал Мегу.

Вот здесь  в папке "Микроконтроллеры 2000-2008" есть книга "Умный дом своими руками (Гололобов)(2007).djvu". Специально даю не прямую ссылку на книгу, а сразу на весь склад, т.к. там до хрена всего интересного, ковыряйтесь, если хотите.

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

с утреца такими крепкими словами разбрасываешься, мы тут еще не проснулись )))

Андрей, не засоряйте тему.

Интересны вам умные дома - создайте свою тему и там спрашивайте. Вот и заодно и тема будет...

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

Мой результат для тестового набора из первого поста:

=== Span selection ===
Span  6x8
Span  9x11
Span  10x12
Span  13x15
Span  14x17
Span  16x18
Span  19x22
Span  24x27
Total value = 6367.66
Calculation time = 2800 us

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

Ясненько :) Ну я еще пооптимизирую :)

У меня больше, чем с 26-ю ключами не работала. Может я ее готовить не умею;)

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

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

Да все равно количество ключей мало о чем говорит. Набор из 26 ключей может быть условно говоря линейным, разветвленным и кольцевым. А так же любой их комбинацией. И в каждом случае число переборов и рекурсий будет разным.

пример давайте, что так обсуждать.

static Spanner spanners[] = {
    {1, 8 , 3},
    {2, 3 , 4},
    {3, 4, 4},
    {4, 5, 4},
    {5, 6, 5},
    {6, 7, 5},
    {7, 8, 5},
    {8, 9, 6},
    {9, 10, 6},
    {10, 11, 7},
    {11, 12, 7},
    {12, 13, 8},
    {13, 14, 8},
    {14, 15, 7},
    {15, 16, 8},
    {16, 17, 7},
    {17, 18, 4},
    {18, 10, 4},
    {19, 20, 4},
    {20, 21, 5},
    {21, 22, 5},
    {22, 23, 5},
    {23, 24, 6},
    {24, 15, 6}
};

С подобным набором (не с  этим, тот код я не сохранил) рекурсия у меня сломалась.

Мое решение:

Ключи
2. 4-5: 0 руб. 4 коп.
3. 17-18: 0 руб. 4 коп.
6. 6-7: 0 руб. 5 коп.
9. 21-22: 0 руб. 5 коп.
12. 9-10: 0 руб. 6 коп.
13. 23-24: 0 руб. 6 коп.
16. 11-12: 0 руб. 7 коп.
20. 13-14: 0 руб. 8 коп.
21. 15-16: 0 руб. 8 коп.
22. 1-8: 0 руб. 3 коп.
23. 2-3: 0 руб. 4 коп.
24. 19-20: 0 руб. 4 коп.
Стоимость набора: 0 руб. 64 коп.
Время расчёта: 210904 миллисекунд

готово

=== Span selection ===
Span  1x8
Span  2x3
Span  4x5
Span  6x7
Span  9x10
Span  11x12
Span  13x14
Span  15x16
Span  17x18
Span  19x20
Span  21x22
Span  23x24
Total value = 0.64
Calculation time = 7948 us

 Calculation time = 7948 us.

Эффективно. Я же говорил, что готовить не умею...

тут не только в Ваших умениях дело, это разница между направленным поиском и полным перебором

Не зря Евгений несколько удивился, когда вы этим путем пошли

Это не со мной разговор был, с АндреемД, но не суть. Я понимал изначально, что тупой перебор неэффективен. Но!

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

По хорошему в решении неплохо было бы объединить оба этих метода - до определенного кол-ва ключей, которые невозможно исключить из анализа, решать перебором, а при большем - "ветвями-границами" Но это не точно;)

С моим "полным" перебором последний набор:

2. 13-14: 0 руб. 8 коп.
3. 15-16: 0 руб. 8 коп.
5. 11-12: 0 руб. 7 коп.
9. 9-10: 0 руб. 6 коп.
10. 23-24: 0 руб. 6 коп.
13. 6-7: 0 руб. 5 коп.
16. 21-22: 0 руб. 5 коп.
19. 4-5: 0 руб. 4 коп.
20. 17-18: 0 руб. 4 коп.
22. 1-8: 0 руб. 3 коп.
23. 2-3: 0 руб. 4 коп.
24. 19-20: 0 руб. 4 коп.
Стоимость набора: 0 руб. 64 коп.
Время расчёта: 748187 миллисекунд

Благодарю за ссылку, почитаю.

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

Спорно. Исходный набор ( тот, что задан Е.П.) - Ваше решение  Calculation time = 2800 us, мое - Время расчёта: 641 миллисекунд. 

английское сокращение uS - это микросекунды, а не милли

Согласен

Погуглил, посмотрел эти "ветви - границы". Простенькая задача.:) Для "новичков":))) Но тем не менее попытаюсь разобраться...

я в теорию не лез. Я код в общем виде уже написал, когда решил поглядеть в интернете, что такое "ветви и границы". Мне показалось, что это именно то, что у меня :)

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

Время еще есть, до конца месяца почти 2 недели. Я свой код выложу через несколько дней, надо поправить кривизну, убрать мусор и еще потестировать.

Хочу предложить еще такой набор для проверки (вполне реальный: https://aliexpress.ru/item/4000127322557.html)

static Spanner spanners[] = {
    {4, 4.5 , 3},
    {4.5, 4 , 4},
    {5.5, 5, 4},
    {6, 5, 4},
    {6, 5.5, 5},
    {7, 6, 5},
    {8, 7, 6},
    {9, 8, 6},
    {10, 9, 7},
    {11, 10, 7}
};

А есть еще и такие интересные наборы, где одна головка метрическая, а другая - дюймовая https://aliexpress.ru/item/33014318147.html

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

Так же "имеется набор несимметричных ключей с известными размерами (по два на ключ)"

Есть ГОСТы на ключи - ссыль, там указаны все возможные размеры ключей и неважно, что там китайцы придумали. И выбираем только те ГОСТы в которых ключи двухсторонние и с разными размерами. Ну и с фиксированными размерами.

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

Я так вижу.

Т.е. желательно дополнить, что значить условие "правильно заданные данные", в частности и про дюймы.

И ключи всё-таки гаечные?

static Spanner spanners[] = {
    {4, 4.5 , 3},
    {4.5, 4 , 4},
    {5.5, 5, 4},
    {6, 5, 4},
    {6, 5.5, 5},
    {7, 6, 5},
    {8, 7, 6},
    {9, 8, 6},
    {10, 9, 7},
    {11, 10, 7}
};

Кроме того  задача от Е.П.  с Вашим набором просто не скомпилируется - размер ключа задан как uint8_t.

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

static Spanner spanners[] = {
    {4, 45 , 3},
    {45, 4 , 4},
    {55, 5, 4},
    {6, 5, 4},
    {6, 55, 5},
    {7, 6, 5},
    {8, 7, 6},
    {9, 8, 6},
    {10, 9, 7},
    {11, 10, 7}
};

Ну, ГОСТ я посмотрел еще до Вашей наводки и обнаружил там размеры не кратные 0.5 мм.

С другой стороны, пример набора ключей взят именно с китайского сайта, так что положения ГОСТ СССР/РФ как-то имеют ну очень мало отношения к тем наборам, что можно купить на Али.

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

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

Я, кстати, заглядывал в Вашу программу - Вы очень неэффективно расходуете память. А с точки зрения 16 МГц процессора при 2 Кбайтах ОЗУ умение грамотно использовать память, пожалуй, даже более важное, чем умение распорядиться производительностью.

В принципе, при подведении итогов IMHO имело бы смысл сравнивать исходники не только по скорости, но и максимальному количеству допустимых элементов для сравнения.

static Spanner spanners[] = {
    {4, 4.5 , 3},
    {4.5, 4 , 4},
    {5.5, 5, 4},
    {6, 5, 4},
    {6, 5.5, 5},
    {7, 6, 5},
    {8, 7, 6},
    {9, 8, 6},
    {10, 9, 7},
    {11, 10, 7}
};

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

static Spanner spanners[] = {
    {4, 45 , 3},
    {45, 4 , 4},
    {55, 5, 4},
    {6, 5, 4},
    {6, 55, 5},
    {7, 6, 5},
    {8, 7, 6},
    {9, 8, 6},
    {10, 9, 7},
    {11, 10, 7}
};

А можно ли?

Уже упоминавшийся выше ГОСТ допускает ключи размером как 5.5, так и 55 мм. Как Вы их планируете различать?

PS. Лично я, опираясь на статистику китайского сайта, указывал размеры метрических ключей в единицах 0.5 мм, а дюймовых - 5 бит на числитель и 2 бита на знаменатель. Оставшийся бит, соответственно, на выбор между дюймовым и метрическим. И тогда все прекрасно помещается 1 байт. Просто надо для каждой предметной области тщательно продумывать структуру данных, а не тупо в лоб "тогда считаем в десятых...".

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

Как справедливо заметил b707 размеры - просто метки. Я бы тупо "переименовал" бы эти странные размеры в "А,Б,,,,К" , оперировал бы ими, а при печати результата сделал бы обратное "переименование".

Так я не спорю. Но на мой взгляд это несущественные мелочи.

Повторюсь, размеры - это не более чем метки, никакого собственного смысла эти обозначения 5, 5.5 и 3/2 не несут. Как именно указывать в таблице конкретные размеры - это только вопрос кодирования. собственно к задаче оптимизации это отношения не имеет. В отличии, например, симметричных ключей, под которые надо кардинально менять алгоритм.

отличная идея. В начале работы просто кодируем размеры целыми числами в пределах байта, на выходе - делаем обратную перекодировку.  И можно использовать хоть 11.0625 или даже символьные имена типа "полдюйма" :)))

Разница между мной и студентом - 30 лет, в течение которых я практически не занимался умственной работой. Стал замечать, что воспринимать новое стало заметно тяжелее. То, с чем в молодости я мог разобраться за час сегодня требует часов, а то и дней:(( Это основная причина, по которой я занялся программированием - потренировать мозги...

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

Кстати, наиболее грамотное решение.

Необязательно "А...К", достаточно просто целыми числами, укладывающимися в определенное количество битов.

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

То есть в проверочном наборе размеры ключей должны быть целочисленными от 1 до 255. Так?

Как хотите. Я бы не выпендривался :-)

0  мне нужен отдельно в новой идее кода, который я ещё не доделал. Чтобы не вводить ещё один булевый массив.