Arduino.ru

"когда в обществе нет цветовой дифференциации штанов то нет и цели"

Со временем выполнения тут есть некая странность. Я уже описывал в #154. Кроме того, проверял код АндреяД, в 1.8.7 исполняется дольше (мой, наоборот, быстрее). А в 1.8.13 - код АндреяД у меня и у него выполняются за одинаковое время.

Да, у меня получился алгоритм для определённых типов стартовых наборов, сделать его универсальным у меня не получилось.

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

Spanner(const uint8_t s1, const uint8_t s2, const uint32_t p, const bool ini = false, const uint8_t s2s1 = 0) 
    :  price(p), size1(s1), size2(s2), included(ini), size2size1(s2s1) {}
  
  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
// Размеры в одном ключе не равны между собой и не равны 0
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[totalSpanners * 2], cSizes[totalSpanners * 2];  

// Функция удаления размера ключа из массива размеров ключей
void delSize(uint8_t dSize, uint8_t aSizes) {
  for (uint8_t i = 0; i < aSizes; i++)
    if (sizes[i] == dSize) {sizes[i] = 0; break;}
}

// Функция проверки наличия размера в массиве размеров
bool provSize (uint8_t pSize, uint8_t aSizes) {
  for (uint8_t i = 0; i < aSizes; i++)
    if (sizes[i] == pSize) return 1;
  return 0;
}


void doCalculations(void) {
  Spanner tempS[] = {{0,0,0}};
  bool flag1=0, flag2=0; 
  uint8_t totalSpanners1=0, dbl=0, allSizes=0, temp8=0, iKey=0;
  
  memset(sizes, 0, sizeof(sizes[0]) * (totalSpanners * 2)); // Обнуление массива размеров.
  memset(cSizes, 0, sizeof(cSizes[0]) * (totalSpanners * 2)); // Обнуление массива кол-ва одинаковых размеров.

  // Поиск более дорогих дублей
  for (uint8_t i=0; i < totalSpanners; i++) 
    for (uint8_t j=0; j < totalSpanners; j++) 
      if (!spanners[j].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 = 1;

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

  totalSpanners1 = totalSpanners - dbl; // Кол-во ключей без дублей
  totalSpanners2 = totalSpanners1; // Для вывода результата

  // Проверка, что второй размер больше первого в ключах и вычисление разницы размеров в каждом ключе.
  for (uint8_t i = 0; i < totalSpanners1; i++) {
    if (spanners[i].size1 > spanners[i].size2) {
      temp8 = spanners[i].size1;
      spanners[i].size1 = spanners[i].size2;
      spanners[i].size2 = temp8;
    }
    spanners[i].size2size1 = spanners[i].size2 - spanners[i].size1;
  }
  
  // Поиск всех размеров ключей и кол-ва каждого размера
  for (uint8_t i = 0; i < totalSpanners1; 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;
  }

  // Добавление ключей с одним размером в результирующий набор и исключение второго размера ключа из массива размеров
  for (uint8_t i = 0; i < totalSpanners1; i++) 
    for (uint8_t j=0; j < allSizes; j++) 
        if (cSizes[j] == 0) {
          if (sizes[j] == spanners[i].size1) {
            spanners[i].included = 1;
            delSize(spanners[i].size2, allSizes);
          }  
          if (sizes[j] == spanners[i].size2) {
            spanners[i].included = 1;
            delSize(spanners[i].size1, allSizes);
          }
        }
        
  // Исключение одиночных размеров из массива размеров    
  for (uint8_t j=0; j < allSizes; j++) 
    if (cSizes[j] == 0) sizes[j] = 0;

  flag1 = 1; 
  // Основной цикл
  while (flag1) {
    for (uint8_t i = 0; i < allSizes; i++) {
      if (sizes[i] == 0) continue;
      temp8=0;
      for (uint8_t j=0; j < totalSpanners1; j++) {
        if (spanners[j].size1 == sizes[i]) {
          if (provSize(spanners[j].size2, allSizes)) {
            if (temp8 == 0) {temp8 = spanners[j].size2size1; iKey = j;}
            else if (spanners[j].size2size1 > spanners[iKey].size2size1)
              {temp8 = spanners[j].size2size1; iKey = j;}
          }
        } 
        if (spanners[j].size2 == sizes[i]) {
          if (provSize(spanners[j].size1, allSizes)) {
            if (temp8 == 0) {temp8 = spanners[j].size2size1; iKey = j;}
            else if (spanners[j].size2size1 > spanners[iKey].size2size1)
              {temp8 = spanners[j].size2size1; iKey = j;}
          }
        }
      }
      if (temp8 != 0) {
        spanners[iKey].included = 1;
        delSize(spanners[iKey].size1, allSizes);
        delSize(spanners[iKey].size2, allSizes);
      }
    }
    // Проверка, что все размеры исключены из массива размеров
    flag1=0;
    for (uint8_t i = 0; i < allSizes; i++) if (sizes[i] > 0) flag1=1;
  }

}

void printResults(void) {
  Serial.println("Ключи");
  uint32_t total = 0;
  for (uint8_t i = 0; i < totalSpanners2; i++) {
    if (spanners[i].included) {
      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) {}  

Результат:

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

 

 

Андрей! это ПАТАМУШТА задачу решить пытаешься чисто математически, а она всё таки прикладная, размеры ключей в паре формируются не с потолка, а из ограничений на усилия, то-есть с ключом на 10 не может быть в паре размерность к примеру 17 (и выше) подумай, как это можно обыграть, да никто не мешает тебе сделать массив размерностей (5,6,7...) и его использовать, они стандартизированы и, смотришь, в один проход с дельтой возврата получится реализовать

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

Т.е. на входе имеем совокупность объектов под названием "ключ" с тремя свойствами: 1. первый ненулевой размер; 2. второй ненулевой размер не равный первому. 3. цена.

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

если абстрактная, тогда да

Хех, типа, а вдруг новичок докажет P=NP, просто потому, что не знает об этом?

Поучаствую-ка и я, моё решение вне конкурса и не для ардуины, зато самое быстрое по времени создания - менее 5 минут, решает за 500 мксек, ну правда и цпу пошустрее, чем атмега.

composer require graphp/algorithms graphp/graph graphp/graphviz

<?php
require_once( __DIR__ . "/vendor/autoload.php" );

use Fhaculty\Graph\Graph;
use Graphp\GraphViz\GraphViz;
use Graphp\Algorithms\MinimumSpanningTree\Kruskal;

$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 ]
];

$graph = new Graph;

foreach ( $spanners as $spanner )
{
	$a = $graph->createVertex( $spanner[0], TRUE );
	$b = $graph->createVertex( $spanner[1], TRUE );
	$a->createEdge( $b )
	  ->setWeight( $spanner[2] );
}

$alg    = new Kruskal( $graph );
$result = $alg->createGraph();

$graphviz = new GraphViz();
$graphviz->display( $result );

Таким образом, получаем минимальное остовное дерево, которое нам и требовалось. Понравился прикол с размерами ключей 12-13-15 и 12-14-15. В решении 42 строки, что доказывает, что смысл жизни - в знаниях :)

PS Кто не писал алгоритм для упаковки товаров со свойствами Ш*Д*В в коробки доставки Ш*Д*В - жизни не видел. :)

А Вы думаете,что эта простая и очевидная на первый взгляд, однако неправильная в корне идея осенила только Вас;) Ошибаетесь. Кста и на Ардуине она решается за сопоставимое время, поверьте мне - она у мной написана. Только зто задача не про связный граф, а про множество() графов из двух узлов и одной дуги. И мин. деревом для ЛЮБОГО ключа будет его ЦЕНА. И в верное решение могут входить ключи, которые не входят в остовное, которое Вы изобразили...

kolyn

Да, верно, нужен другой лес, не такой.

а ты все время в чисто программисткую задачу пытаешься внести сермяжный смысл , достойный кладовщика инструментального цеха.
Слушай, мне как програмисту глубоко плевать на размеры по ГОСТу. Программа должна работать с любыми наборами, даже совершенно бредовыми, типа 3х55, иначе это не программа.
И от меня просьба - если тебе нечего сказать по сути конкурса - лучше не говори ничего

Андрей, посмотрел код... никак не могу понять, почему вы сделали ключевой характеристикой поиска не цену, а разницу между размерами на концах ключа. Какое отношение это число имеет к оптимальному набору?  С чего вы взяли, что ключ 14Х17 обязательно выгоднее 17х19 ?

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

Думаю, это влияние ua6em... это он задурил вам готову своими ГОСТами и словами, что размеры ключей должны быть строго определенных комбинаций и заданы в соответвии с реальной линейкой размеров... Это неверно. На самом деле по условию размеры могут быть абсолютно любыми..

У меня получился алгоритм для конкретного набора. Разрабатывал его от правильного результата. Т.е. посмотрел какие должны быть выбраны ключи и как их надо выбирать и нашёл такую закономерность.

Уже делаю другой алгоритм.

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

Набор из задания:

Ключи
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 коп.
14. 6-8: 382 руб. 8 коп.
15. 9-11: 495 руб. 97 коп.
16. 24-27: 1715 руб. 70 коп.
Стоимость набора: 6367 руб. 66 коп.
Время расчёта: 340 миллисекунд

Набор от kolyn:

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

Запустил ГОСТовский набор полностью:

    {1, 2 , 1}, // 2.5 x 3.2
    {2, 4 , 2}, // 3.2 x 4
    {2, 3, 3},  // 3.2 x 5.5
    {4, 5, 4}, 
    {5, 3, 5},  // 5 x 5.5
    {3, 7, 6},  // 5.5 x 7
    {6, 7, 7},
    {7, 8, 8},  
    {8, 9 , 41520},
    {8, 10, 43054},
    {9, 11, 9}, 
    {10, 11, 10},  
    {10, 12, 51455},
    {10, 13, 11}, 
    {11, 12, 12},
    {11, 13, 13},
    {12, 13, 56544},
    {12, 14, 57675},
    {13, 14, 15}, 
    {13, 15, 62845},
    {13, 16, 16}, 
    {13, 17, 17}, 
    {14, 15, 61714},
    {14, 17, 70276},
    {16, 17, 76496},
    {16, 18, 81989},
    {17, 19, 82312},
    {17, 22, 18},
    {18, 19, 82877},
    {18, 21, 19},
    {19, 22, 110826},
    {19, 24, 20},
    {21, 22, 21},
    {21, 24, 22},
    {22, 24, 145560},
    {22, 27, 23}, 
    {24, 27, 171570},
    {24, 30, 24}, 
    {27, 30, 25}, 
    {27, 32, 26}, 
    {30, 32, 27}, 
    {30, 34, 28},
    {30, 36, 29}, 
    {32, 34, 30},  
    {32, 36, 31},
    {34, 36, 32},
    {36, 41, 33},  
    {41, 46, 34},
    {46, 50, 35},
    {50, 55, 36}, 
    {55, 60, 37},
    {65, 70, 38},
    {70, 80, 39}

При компиляции последнего:

Скетч использует 8182 байт (26%) памяти устройства. Всего доступно 30720 байт.
Глобальные переменные используют 1009 байт (49%) динамической памяти, оставляя 1039 байт для локальных переменных. Максимум: 2048 байт.

 

Блин, мужики, Вы меня ну очень приятно удивляете! Спасибо!

Интересно, сколько в итоге будет участников, и сколько будет 100% рабочих вариантов.
Жаль ничего не петрю в алгоритмах и математике, тоже бы поучаствовал. Помню, лет 20 назад участвовал в конкурсе программирования игр, Lines была задача написать. Сколько то шаров одноцветных, несколько двуцветных и один универсальный. Интересно было написать алгоритм проверки на 5 одинаковых цветов в линии. Даже выиграл тогда, но уровень соперников не известен, и никто не написал 100% рабочего варианта, а так хотелось сравнить.

А чем мой предпоследний вариант не рабочий? Он только долгий. Да и у kolyn, вроде рабочие варианты.

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

Я не говорю, что не рабочие. Дождёмся экспертного мнения Евгения Петровича.

Про наборы

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

Вот, к примеру, набор Евгения Петровича:

Видно. что в нем есть ветвления и циклы. Но так же есть и длинные "хвосты", которые сильно облегчают решение.

Добавим к нему всего один ключ - и набор станет совсем другим:

И вот самое интересное - насколько будет отличаться время решения этих двух наборов алгоритмами разных авторов :)

Чисто практически - набор ЕП у меня считается за 2.8 мс, а если добавить к нему ключик со следующими парметрами:

{9, 27, 71570}

то время расчета возрастает сразу до 14.2 мс - ровно в пять раз.

Всего один ключик. а такая разница :)

что считать 100% рабочим вариантом? Зависит от того, как тестировать. Если отбросить явные ошибки алгоритмов, то все упирается в память. Памяти в атмеги328 мало. а очевидно что чем больше ключей - тем быстрее она кончается.

На данный момент у меня есть код, который все небольшие наборы из ветки решает влет :) Но наборах от товарища ua6em он затыкается. Вот уже неделю бьюсь, выкинул из кода все лишнее, выиграл в памяти почти в 2 раза - но до успеха еще очень далеко. Например, набор из сообщения #220 требует для решения 12 уровней рекурсии. А память заканчивается на четвертом :( И хотя каждый следующий уровень меньше предыдущего - все-таки разница между 4 и 12-тью - не очень обнадеживающая :)))

С массивом из 100 ключей пустой скелет выдаёт: Глобальные переменные используют 1210 байт (59%).

Как вариант можно переместить included в несколько uint64_t, а оставшийся массив структур в PROGMEM, если, конечно, никаких манипуляций по изменению массива структур код делать не будет.

 

По моему коду.

Полный ГОСТовский набор у меня за сутки так и не посчитался, если его разделить примерно пополам, обе половины проходят.

Результаты до 30 ключей:

    {1, 2 , 1}, // 2.5 x 3.2
    {2, 4 , 2}, // 3.2 x 4
    {2, 3, 3},  // 3.2 x 5.5
    {4, 5, 4}, 
    {5, 3, 5},  // 5 x 5.5
    {3, 7, 6},  // 5.5 x 7
    {6, 7, 7},
    {7, 8, 8},  // 1 миллисекунда
    {8, 9 , 41520},
    {8, 10, 43054},
    {9, 11, 9}, 
    {10, 11, 10},  
    {10, 12, 51455}, // 28 миллисекунд
    {10, 13, 11}, 
    {11, 12, 12},
    {11, 13, 13},
    {12, 13, 56544},
    {12, 14, 57675}, // 661 миллисекунд
    {13, 14, 15}, 
    {13, 15, 62845},
    {13, 16, 16}, 
    {13, 17, 17}, 
    {14, 15, 61714}, // 12638 миллисекунд
    {14, 17, 70276},
    {16, 17, 76496}, // 162046 миллисекунд
    {16, 18, 81989},
    {17, 19, 82312},
    {17, 22, 18}, // 76581 миллисекунд
    {18, 19, 82877},
    {18, 21, 19}, // 1637374 миллисекунд

Набор из 100 ключей, где 75 дубли по размерам:

    {2, 1 , 1}, // 3.2 x 2.5
    {1, 2 , 2},
    {2, 1 , 3},
    {1, 2 , 4},
    {4, 2 , 4}, // 4 x 3.2 
    {2, 4 , 3},
    {4, 2 , 2},
    {2, 4 , 5},
    {2, 3, 6},  // 3.2 x 5.5
    {2, 3, 3},
    {2, 3, 4},
    {2, 3, 5},
    {5, 4, 6},
    {4, 5, 4},
    {5, 4, 5},
    {4, 5, 7}, 
    {5, 3, 5},  // 5 x 5.5
    {5, 3, 5},
    {5, 3, 5},
    {5, 3, 5},
    {3, 7, 6},  // 5.5 x 7
    {3, 7, 7},
    {3, 7, 8},
    {3, 7, 9},
    {7, 6, 7},
    {6, 7, 7},
    {7, 6, 7},
    {6, 7, 7},
    {7, 8, 8},  
    {7, 8, 8},
    {7, 8, 8},
    {7, 8, 8},
    {8, 9 , 41520},
    {8, 9 , 41521},
    {8, 9 , 41522},
    {8, 9 , 41523},
    {8, 10, 43054},
    {8, 10, 43054},
    {8, 10, 43054},
    {8, 10, 43054},
    {9, 11, 9}, 
    {9, 11, 9},
    {9, 11, 9},
    {9, 11, 9},
    {11, 10, 10},
    {10, 11, 10}, 
    {11, 10, 10}, 
    {10, 11, 10},   
    {10, 12, 51455}, 
    {10, 12, 51456},
    {10, 12, 51457},
    {10, 12, 51458},
    {10, 13, 11}, 
    {10, 13, 11}, 
    {10, 13, 11}, 
    {10, 13, 11}, 
    {11, 12, 15},
    {11, 12, 14},
    {12, 11, 13},
    {12, 11, 12},
    {11, 13, 13},
    {11, 13, 13},
    {11, 13, 13},
    {11, 13, 13},
    {12, 13, 56544},
    {12, 13, 56544},
    {12, 13, 56544},
    {12, 13, 56544},
    {12, 14, 57678}, 
    {12, 14, 57677},
    {12, 14, 57676},
    {12, 14, 57675},
    {13, 14, 16}, 
    {13, 14, 15},
    {13, 14, 17},
    {14, 13, 18},
    {13, 15, 62845},
    {13, 15, 62846},
    {13, 15, 62847},
    {13, 15, 62848},
    {13, 16, 16},
    {13, 16, 16}, 
    {13, 16, 16}, 
    {13, 16, 16},  
    {13, 17, 17}, 
    {13, 17, 17},
    {13, 17, 17},
    {13, 17, 17},
    {15, 14, 61718},
    {14, 15, 61716},
    {14, 15, 61717},
    {15, 14, 61714},
    {14, 17, 70276},
    {14, 17, 70276},
    {14, 17, 70276},
    {14, 17, 70276},
    {16, 17, 76498},
    {16, 17, 76499},
    {17, 16, 76496},
    {16, 17, 76497}

Компилятор:

Скетч использует 9908 байт (32%) памяти устройства. Всего доступно 30720 байт.
Глобальные переменные используют 1506 байт (73%) динамической памяти, оставляя 542 байт для локальных переменных. Максимум: 2048 байт.

Результат:

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

Результат набора с добавлением {9, 27, 71570} в набор из задания:

Ключи
2. 22-24: 1455 руб. 60 коп.
4. 18-19: 828 руб. 77 коп.
7. 16-17: 764 руб. 96 коп.
8. 9-27: 715 руб. 70 коп.
11. 14-15: 617 руб. 14 коп.
13. 12-13: 565 руб. 44 коп.
15. 8-10: 430 руб. 54 коп.
16. 6-8: 382 руб. 8 коп.
17. 9-11: 495 руб. 97 коп.
Стоимость набора: 6256 руб. 20 коп.
Время расчёта: 1828 миллисекунд

Набор из 100 ключей, где 75 дубли по размерам или уникальные ключи (т.е. оба размера ключа больше не присутствуют):

    {2, 1 , 1}, // 3.2 x 2.5
    {18, 19 , 2},
    {20, 21 , 3},
    {24, 25 , 4},
    {4, 2 , 4}, // 4 x 3.2 
    {2, 4 , 3},
    {4, 2 , 2},
    {2, 4 , 5},
    {2, 3, 6},  // 3.2 x 5.5
    {2, 3, 3},
    {2, 3, 4},
    {2, 3, 5},
    {5, 4, 6},
    {4, 5, 4},
    {5, 4, 5},
    {4, 5, 7}, 
    {5, 3, 5},  // 5 x 5.5
    {5, 3, 5},
    {5, 3, 5},
    {5, 3, 5},
    {3, 7, 6},  // 5.5 x 7
    {3, 7, 7},
    {3, 7, 8},
    {3, 7, 9},
    {7, 6, 7},
    {6, 7, 7},
    {7, 6, 7},
    {6, 7, 7},
    {7, 8, 8},  
    {7, 8, 8},
    {7, 8, 8},
    {7, 8, 8},
    {8, 9 , 41520},
    {8, 9 , 41521},
    {8, 9 , 41522},
    {8, 9 , 41523},
    {8, 10, 43054},
    {8, 10, 43054},
    {8, 10, 43054},
    {8, 10, 43054},
    {9, 11, 9}, 
    {9, 11, 9},
    {9, 11, 9},
    {9, 11, 9},
    {11, 10, 10},
    {10, 11, 10}, 
    {26, 27, 10}, 
    {29, 28, 10},   
    {30, 31, 51455}, 
    {10, 12, 51456},
    {10, 12, 51457},
    {10, 12, 51458},
    {10, 13, 11}, 
    {10, 13, 11}, 
    {10, 13, 11}, 
    {10, 13, 11}, 
    {11, 12, 15},
    {11, 12, 14},
    {12, 11, 13},
    {12, 11, 12},
    {11, 13, 13},
    {11, 13, 13},
    {11, 13, 13},
    {11, 13, 13},
    {12, 13, 56544},
    {32, 33, 56544},
    {34, 35, 56544},
    {36, 37, 56544},
    {12, 14, 57678}, 
    {12, 14, 57677},
    {12, 14, 57676},
    {12, 14, 57675},
    {13, 14, 16}, 
    {13, 14, 15},
    {13, 14, 17},
    {14, 13, 18},
    {13, 15, 62845},
    {13, 15, 62846},
    {13, 15, 62847},
    {13, 15, 62848},
    {13, 16, 16},
    {39, 38, 16}, 
    {40, 41, 16}, 
    {42, 43, 16},  
    {13, 17, 17}, 
    {13, 17, 17},
    {13, 17, 17},
    {13, 17, 17},
    {15, 14, 61718},
    {14, 15, 61716},
    {14, 15, 61717},
    {15, 14, 61714},
    {14, 17, 70276},
    {14, 17, 70276},
    {14, 17, 70276},
    {14, 17, 70276},
    {16, 17, 76498},
    {16, 17, 76499},
    {17, 16, 76496},
    {16, 17, 76497}

Результат:

Ключи
4. 15-14: 617 руб. 14 коп.
10. 13-17: 0 руб. 17 коп.
11. 13-16: 0 руб. 16 коп.
14. 12-11: 0 руб. 12 коп.
16. 10-11: 0 руб. 10 коп.
17. 9-11: 0 руб. 9 коп.
18. 7-8: 0 руб. 8 коп.
20. 5-3: 0 руб. 5 коп.
23. 4-2: 0 руб. 2 коп.
24. 2-1: 0 руб. 1 коп.
25. 18-19: 0 руб. 2 коп.
26. 20-21: 0 руб. 3 коп.
27. 24-25: 0 руб. 4 коп.
28. 6-7: 0 руб. 7 коп.
29. 26-27: 0 руб. 10 коп.
30. 29-28: 0 руб. 10 коп.
31. 30-31: 514 руб. 55 коп.
32. 32-33: 565 руб. 44 коп.
33. 34-35: 565 руб. 44 коп.
34. 36-37: 565 руб. 44 коп.
35. 39-38: 0 руб. 16 коп.
36. 40-41: 0 руб. 16 коп.
37. 42-43: 0 руб. 16 коп.
Стоимость набора: 2829 руб. 65 коп.
Время расчёта: 162206 миллисекунд

Буду благодарен, если предложите наборы для тестирования, на условиях:

// Ключей в массиве не больше 100
// Размеры в одном ключе целочисленные, не равны 0, не равны между собой, и каждый не больше 255
// При наличии пресекающихся по размерам ключей в кол-ве больше 30 вычисления займут длительное время

 

Нашел в коде серьезный косяк. Исправленная версия:

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

  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},
  {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]);
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; //Вычислили мин. возможное кол-во ключей
  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();
}
//--------------------------------------------------



//
// Функция пeребора вариантов сочетаний ключей
//
void  bruteForce(uint8_t minQ, uint8_t qOff, uint8_t qOn, uint8_t qSize)
{
  uint8_t tempArr[qOff];
  uint32_t tempTotal = 4294967295;
  bool complectYes = false;

  for ( minQ; minQ <= qOff + qOn; minQ++)
  { //Serial.println(minQ);
    bool flagComplect = false;
    uint8_t *currArr;
    currArr = new uint8_t[minQ - qOn];


    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)                  //если собрался правильный набор набор
    {
      uint32_t currTotal = 0;
      for (uint8_t i = 0; i < qOff + qOn; i++)                   //подсчитали цену
      {
        if (spanners[i].included == on)
          currTotal += spanners[i].price;
      }
      if (currTotal <= tempTotal)            //если цена  меньше записанной или это первый набор
      {
        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;                            //записываем в темп аррей
        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))                          //если собрался правильный набор набор
      {
        uint32_t currTotal = 0;
        for (uint8_t i = 0; i < qOff + qOn; i++)                   //подсчитали цену
        {
          if (spanners[i].included == on)
          {
            currTotal += spanners[i].price;
          }
        }
        if  (currTotal <= tempTotal )                              //если цена  меньше записанной или это первый набор
        {
          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;                           //записываем в темп аррей
          }
          flagComplect = true;                                     //поднимаем флаг "собран комплект"
        }
      }

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

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

    if (flagComplect == true)                                      // комплект был создан мин.1 раз
      complectYes = true;

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

    if ( qOff == minQ + qOn)                                            //Последняя иттер.
    {
      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="<a href="<a href="https://prog-cpp.ru/combinations/" 
//
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[] = {{0, 0, 0}};
  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++;
    }
  }
  //Serial.print(uniqueSpanner);
  return uniqueSpanner;

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

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

      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;
      }
    }

  }
  for (uint8_t i = 0; i < totalSpanners * 2; i++)
  {
    uint8_t j = 0;
    while (j < i && arrSize[j] != arrSize[i])
      ++j;

    if (j == i)
      inSize ++;
  }
  //Serial.print(inSize);

  return inSize;
}

//-------------------------------------------------------



//
// функция сортировки ключей от дешевых к дорогим
//
void spanSort(Spanner * spanarray)
{
  Spanner tmp[] = {{0, 0, 0}};
  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();
  const uint32_t duration = millis() - start;
  printResults();
  Serial.print("Время расчёта: ");
  Serial.print(duration);
  Serial.println(" миллисекунд");
}

void loop(void) {}

Результат выполнения в 1.8.13

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

К сожалению в плане оптимизации по времени ничего не выжал. При переборе с пом. "сочетаний без повторений" метод ветвей - границ в полной мере применить не сумел.

 

Тоже использую сочетания без повторений, но немного по другому. Подсказка. :) Время исполнения моего алгоритма примерно половина от вашего времени. Хотя, может о чём я думаю уже у вас реализовано, не вникал в ваш код.

И ещё появилась идея как ускорить, думаю, за выходные успею до ума довести.

Выложу свой код, а то сроки подходят к концу

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

Зато мелкие наборы считает быстро

Код:

// ver 4.5a 23-11-20
// Remove sindex
// replace original sizes in spanners for 1,2,3...
// remove all non-needed variables in Size and Spanners

#define MAX_SIZE 85
#define MAX_VARIANTS 8
#define NO_INDEX -1

//#define DEBUG

// ++++++ TESTS ++++++
#define TEST_EP
//#define TEST_kolyn
//#define TEST_BIG
//#define GOST30


#ifdef DEBUG
#define DEBUG_PRINT(x)     Serial.print(x)
#define DEBUG_PRINTF(x)     Serial.print(F(x))
#define DEBUG_PRINTLN(x)  Serial.println(x)
#define DEBUG_PRINTDEC(x)     Serial.print(x, DEC)

#else
#define DEBUG_PRINT(x)
#define DEBUG_PRINTF(x)
#define DEBUG_PRINTDEC(x)
#define DEBUG_PRINTLN(x)
#endif 
void memRep(uint8_t str, uint8_t level);



/// Spanner class=================
struct Spanner {
	long price;
	uint8_t size1;
	uint8_t size2;
	//int8_t incl;  // - not needed it

	Spanner(const uint8_t s1, const uint8_t s2, const long pr, const bool in = false) :
		price(pr), size1(s1), size2(s2)     {}

	uint8_t get_other_size_for_span(uint8_t fst_size) {
		if (fst_size == size1) return size2;
		return size1;
	}
	long get_price() {
		return price;
	}
};
/// end of Spanner

#ifdef GOST30
static Spanner spanners[] = {
{1, 2, 1}, // 2.5 x 3.2
{ 2, 4 , 2 }, // 3.2 x 4
{ 2, 3, 3 },  // 3.2 x 5.5
{ 4, 5, 4 },
{ 5, 3, 5 },  // 5 x 5.5
{ 3, 7, 6 },  // 5.5 x 7
{ 6, 7, 7 },
{ 7, 8, 8 },  // 1 миллисекунда
{ 8, 9 , 41520 },
{ 8, 10, 43054 },
{ 9, 11, 9 },
{ 10, 11, 10 },
{ 10, 12, 51455 }, // 28 миллисекунд
{ 10, 13, 11 },
{ 11, 12, 12 },
{ 11, 13, 13 },
{ 12, 13, 56544 },
{ 12, 14, 57675 }, // 661 миллисекунд
{ 13, 14, 15 },
{ 13, 15, 62845 },
{ 13, 16, 16 },
{ 13, 17, 17 },
{ 14, 15, 61714 }, // 12638 миллисекунд
{ 14, 17, 70276 },
{ 16, 17, 76496 }, // 162046 миллисекунд
//{ 16, 18, 81989 },
//{ 17, 19, 82312 },
//{ 17, 22, 18 }, // 76581 миллисекунд
//{ 18, 19, 82877 },
//{ 18, 21, 19 }, // 1637374 миллисекунд 

//{ 21, 15, 61714 }, // 12638 миллисекунд
//{ 24, 17, 70276 },
//{ 26, 17, 76496 }, // 162046 миллисекунд
//{ 26, 18, 81989 },
//{ 17, 18, 82312 },

};
#endif

#ifdef TEST_kolyn
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}
};
#endif
#ifdef TEST_BIG
static Spanner spanners[] = {
  {1, 8 , 3},
  {2, 3 , 4},
  {1, 3 , 4},
  {3, 4, 4},
  {4, 5, 4},
  {5, 6, 5},
  {5, 6, 7},
  {6, 7, 5},
  {7, 8, 5},
  {7, 1, 3},
  {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, 0},
  {22, 23, 5},
  {23, 24, 6},
  {24, 15, 6},
  
  
};
#endif
#ifdef TEST_EP
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},
//	{9, 27, 71570},

};
#endif

static constexpr uint8_t Span_q = sizeof(spanners) / sizeof(spanners[0]);

/// Size class=================
struct Size {
	uint8_t span_cnt;
	uint8_t spans[MAX_VARIANTS];
	
    Size(const uint8_t sp) :
		span_cnt(1) {
		spans[0] = sp;
	}

	Size(const Size* ss) :
		span_cnt(ss->span_cnt)
	{
		memcpy(spans, ss->spans, sizeof(spans));
	}


	uint8_t add_span(uint8_t sp,  uint8_t sz, uint8_t ot_sz, Size* other_size, int8_t* sp_incl) {
		uint8_t s = 0;
		
		while ((s < span_cnt) && (ot_sz != spanners[spans[s]].get_other_size_for_span(sz))) { s++; }
		if (s < span_cnt) {
			
			uint32_t price = spanners[sp].get_price();
			if (price < spanners[spans[s]].get_price()) {
				del_span(spans[s]); 
				other_size->del_span(spans[s]);
				sp_incl[spans[s]] = -1;
			}
			else {
				sp_incl[sp] = -1;
				return 1;
			}  
		}
		add_span(sp);
		return 0;
	}
	void add_span(uint8_t sp) {
		uint32_t price = spanners[sp].get_price();
		uint8_t s = 0;
		while ((s < span_cnt) && (price > spanners[spans[s]].get_price())) { s++; }
		for (uint8_t ii = span_cnt; ii > s; ii--) spans[ii] = spans[ii-1];
		spans[s] = sp;
		span_cnt++;
	}

	int8_t del_span(uint8_t sp) {
		uint8_t ii = 0;
		uint8_t sp_num = 0;
		while (spans[sp_num] != sp && sp_num < span_cnt) { sp_num++; }
		if (sp_num >= span_cnt) return -1;
		for (ii = sp_num + 1; ii < span_cnt; ii++) spans[ii - 1] = spans[ii];
		span_cnt--;
#ifdef DEBUG
		uint8_t s1 = spanners[sp].size1;
		uint8_t s2 = spanners[sp].size2;
		
		DEBUG_PRINT("Span ");
		DEBUG_PRINT(s1);
		DEBUG_PRINT("x");
		DEBUG_PRINT(s2);
		DEBUG_PRINTLN(" deleted ");
#endif
		
		return span_cnt;
	}

	void select_size() {
		span_cnt = 0;
	}

	uint8_t lowest_price_span() {
		return spans[0];
	}

};
/// end of Size


// Global variables

uint8_t* size_table;
Size** sizes;
uint8_t sizes_cnt = 0;
int8_t sp_incl[Span_q] = { 0 };
int8_t best_incl[Span_q] = { 0 };
/************************************************/
long select_span(uint8_t sp, int8_t* span_incl, Size** s_cur) {

	DEBUG_PRINT("Span ");
	DEBUG_PRINT(sp);
    DEBUG_PRINTLN(" selected ");
	span_incl[sp] = 1;
	s_cur[spanners[sp].size1]->select_size();
	s_cur[spanners[sp].size2]->select_size();
  return spanners[sp].price;
}
/************************************************/
//Count unique sizes in spanners set
/************************************************/
void count_sizes() {
	uint8_t ii, jj;
	size_table = (uint8_t*)malloc(MAX_SIZE * sizeof(uint8_t));
	int8_t* index = (int8_t*)malloc(MAX_SIZE * sizeof(int8_t));
	memset(index, NO_INDEX, MAX_SIZE);
	DEBUG_PRINTF("Span count = ");
	DEBUG_PRINTLN(Span_q);
	for (ii = 0; ii < Span_q; ii++) {
		uint8_t ss[] = { spanners[ii].size1, spanners[ii].size2 };
		for (jj = 0; jj < 2; jj++) {
			
			if (index[ss[jj]] == NO_INDEX)
			{
				index[ss[jj]] = sizes_cnt;
				size_table[sizes_cnt] = ss[jj];
				sizes_cnt++;
			}
		}
		spanners[ii].size1 = index[ss[0]];
		spanners[ii].size2 = index[ss[1]];

	}
	free(index);
	realloc(size_table, sizes_cnt);
}/************************************************/
//Create graph with sizes as nodes and spanners as edges
/************************************************/
void create_sizes(int8_t* sp_incl) {
	uint8_t ii, jj;

	for (ii = 0; ii < Span_q; ii++) {
		if (0 == spanners[ii].get_price()) sp_incl[ii] = 1;
		uint8_t ss[] = { spanners[ii].size1, spanners[ii].size2 };
		for (jj = 0; jj < 2; jj++) {
			uint8_t s = ss[jj];
			if (sizes[s] == 0)
			{
				sizes[s] = new Size( ii);
			}
			else {
				if (jj == 0) {
					if (sizes[s]->add_span(ii, ss[0], ss[1], sizes[ss[1]], sp_incl)) jj = 2;
				}
				else sizes[s]->add_span(ii);
			}
		}
	}
	DEBUG_PRINTF("Add sizes ");
	DEBUG_PRINTLN(sizes_cnt);
}
/************************************************/
// Initial test of graph net
/************************************************/

long begin_sort(int8_t* span_incl, Size** s_cur, long cur_min) {
	uint8_t ii;
  long cur_value =0;
  bool changed = true;
	
  for (ii = 0; ii < Span_q; ii++) { if (span_incl[ii] == 1) cur_value += spanners[ii].price; }
  if (cur_value > cur_min) {DEBUG_PRINTLN(" over value ");return cur_value;}
	
	while (changed) {
	
        for (ii = 0; ii < sizes_cnt; ii++) {
			
          Size* s1 = s_cur[ii];
				if (s1->span_cnt == 1) {
					cur_value+=select_span(s1->spans[0], span_incl, s_cur);
				}
			}
	
    if (cur_value > cur_min) {DEBUG_PRINTLN(" over value ");return cur_value;}
		changed = false;
		for (ii = 0; ii < Span_q; ii++) {

			if (span_incl[ii] == 0) {
				Size* s1 = s_cur[spanners[ii].size1];
				Size* s2 = s_cur[spanners[ii].size2];
				if ((s1->span_cnt == 0) && (s2->span_cnt == 0)) {
					changed = true;
					span_incl[ii] = -1;
				}

				else if ((s1->span_cnt == 0) != (s2->span_cnt == 0)) {
					Size* s_w = s1;
					if (s1->span_cnt == 0) s_w = s2;
					if (ii != s_w->lowest_price_span()) {
						if (s_w->del_span(ii) >= 0) { changed = true; span_incl[ii] = -1; }
					}
				}

			}
		}
	}
 return cur_value;
}
/************************************************/
// test is current solution is complete and calculate the value
/************************************************/
long test_solution(int8_t* span_incl, Size** s_cur) {
	uint8_t ii;
	long jj = 0;
  int8_t factor = 1;

  for (ii = 0; ii < sizes_cnt; ii++) {
	  if (s_cur[ii]->span_cnt != 0) {
		  factor = -1;
		  break;
	  }
  }
	for (ii = 0; ii < Span_q; ii++) {
		if (span_incl[ii] == 1)
		{
			jj += spanners[ii].price;
		}
	}
	return (jj*factor);
}

/************************************************/
uint8_t select_edges(uint8_t* edges, Size** s_cur) {
	uint8_t ii, jj = 0;
	while (jj < sizes_cnt) {

		if (s_cur[jj]->span_cnt > 1) {
			for (ii = 0; ii < s_cur[jj]->span_cnt; ii++) { edges[ii] = s_cur[jj]->spans[ii]; }
			return s_cur[jj]->span_cnt;
		}
		jj++;
	}
	return 0;
}
/************************************************/
uint8_t select_edges2(uint8_t* edges, Size** s_cur, uint8_t st) {
	uint8_t ii, jj = 0;
	Size* s1 = s_cur[st];

	if (s1->span_cnt > 1) {
		for (ii = 0; ii < s1->span_cnt; ii++) { edges[ii] = s1->spans[ii]; }
		return s1->span_cnt;
	}

	return 0;
}
/************************************************/
// find center of graph for using it as initial point
/************************************************/
uint8_t find_center(int8_t* span_incl, Size** s_cur) {

	uint8_t changed = 1;
	while (changed) {
		changed = 0;
		uint8_t changed_sizes[16] = { 0 };
		for (uint8_t ii = 0; ii < Span_q; ii++) {

			if (span_incl[ii] == 0) {
				Size* s1 = s_cur[spanners[ii].size1];
				Size* s2 = s_cur[spanners[ii].size2];
				Size* s_w = s1;
				uint8_t sz = spanners[ii].size1;
				if ((s1->span_cnt == 0) != (s2->span_cnt == 0)) {
					if (s1->span_cnt == 0) {
						s_w = s2;
						sz = spanners[ii].size2;
					}
					uint8_t del_result = s_w->del_span(ii);
					if (del_result > 0) {
					
						changed_sizes[changed++] = sz;
						span_incl[ii] = -1;
					}
					else if (del_result == 0) {
						DEBUG_PRINTF("Center size for iteration = ");
						DEBUG_PRINTLN(sz);
						return sz;
					}
				}
			}
		}
		for (uint8_t ii = 0; ii < changed; ii++) {
			Size* s1 = s_cur[changed_sizes[ii]];
			s1->span_cnt =0;
		}
	}
	for (uint8_t ii = 0; ii < Span_q; ii++) {
		if (span_incl[ii] == 0) {
			DEBUG_PRINTF("Res size for iteration = ");
			DEBUG_PRINTLN(spanners[ii].size1);
			return spanners[ii].size1;
		}
	}
}


/************************************************/
void del_sizes2(Size** dest, Size** source) {
	uint8_t ii, jj;
	//for (ii = 0; ii < sizes_cnt; ii++) {
   for (jj = sizes_cnt; jj > 0; jj--) {
    ii = jj-1;
		//if (sss[ii] != 0) delete sss[ii];
		if ((dest[ii] != 0) && (dest[ii] != source[ii])) delete dest[ii];
	}
}
/************************************************/
void init_sizes(Size** dest) {
	uint8_t ii;
	for (ii = 0; ii < sizes_cnt; ii++) { dest[ii] = 0; }

}
/************************************************/
void cp_sizes3(Size** dest, Size** source) {
  
  uint8_t ii;
  for (ii = 0; ii < sizes_cnt; ii++) {
    
    if (source[ii]->span_cnt != 0) {
      if (dest[ii] != 0) *(dest[ii]) = *(source[ii]);
      else dest[ii] = new Size(source[ii]);
      }
    else {
      if ((dest[ii] != 0) && (dest[ii] != source[ii])) delete dest[ii];
      dest[ii] = source[ii];
    }
  }
}
/************************************************/
// main iteration routine
/************************************************/
long minimum_find(int8_t* span_incl, Size** s_cur, long cur_min, uint8_t level) {

	// test for solution
	level++;
	DEBUG_PRINTF("====  enter to new level ");
	DEBUG_PRINTLN(level);
	bool min_found = false;
	long new_min = test_solution(span_incl, s_cur);
	if (new_min >= 0) {
		DEBUG_PRINTF("New solution found! min = ");
		DEBUG_PRINTLN(new_min);
    if (new_min < cur_min) memcpy(best_incl, span_incl, Span_q * sizeof(int8_t));
		return new_min;
	}
	else {
		DEBUG_PRINTF("non-full set val = ");
        DEBUG_PRINTLN(new_min);
		if ((new_min * (-1)) < cur_min) {
			DEBUG_PRINTLN("go next");
			uint8_t k = 0;
			int8_t* new_s_incl = (int8_t*)malloc(Span_q * sizeof(int8_t));
			if (!new_s_incl) memRep(1, level);
			Size** new_sizes = (Size**)malloc( sizes_cnt * sizeof(Size*) );
			if (! new_sizes) memRep(3,level);
			init_sizes(new_sizes);
			uint8_t new_edges[MAX_VARIANTS] = { 0 };
			// select start size
			memcpy(new_s_incl, span_incl, Span_q * sizeof(int8_t));
			cp_sizes3(new_sizes, s_cur);
			uint8_t start_size = find_center(new_s_incl, new_sizes);
			uint8_t var_cnt = select_edges2(new_edges, s_cur, start_size);
			for (k = 0; k < var_cnt; k++) {
				memcpy(new_s_incl, span_incl, Span_q * sizeof(int8_t));
				cp_sizes3(new_sizes, s_cur);
				DEBUG_PRINTF("====  new edge at level ");
				DEBUG_PRINTLN(level);
				select_span(new_edges[k], new_s_incl, new_sizes);
				new_min = begin_sort(new_s_incl, new_sizes, cur_min);
				if (new_min < cur_min) {
					new_min = minimum_find(new_s_incl, new_sizes, cur_min, level);
					if (new_min < cur_min) {
						cur_min = new_min;
						min_found = true;
					}
				}
			}
			if (min_found) {
				new_min = cur_min;
			}

			del_sizes2(new_sizes, s_cur);
			free(new_sizes);
			free(new_s_incl);
			return new_min;
		}
		else {DEBUG_PRINTLN("exit"); 
		return (new_min * (-1));}

	}
}

/************************************************/
void print_spans(int8_t* sp_incl) {
	uint8_t ii;
	long jj = 0;
	Serial.println(F("=== Span selection ==="));
	for (ii = 0; ii < Span_q; ii++) {
		if (sp_incl[ii] == 1)
		{
			uint8_t s1 = size_table[spanners[ii].size1];
			uint8_t s2 = size_table[spanners[ii].size2];
			jj += spanners[ii].price;
			Serial.print("Span  ");
			Serial.print(s1);
			Serial.print("x");
			Serial.println(s2);
		}
	}
	Serial.print(F("Total value = "));
	Serial.println(jj / 100.0, 2);
}
/************************************************/
void memRep(uint8_t str, uint8_t level) {
  Serial.print(F("Not enough memory at level "));
  Serial.println(level);
  switch(str) {
    case 1: Serial.println(F("new_incl"));break;
    case 3: Serial.println(F("sizes"));break;
  }
  while(1);
}
/************************************************/
void setup() {
	// put your setup code here, to run once:
	uint8_t ii;
	long minimum=0;
	Serial.begin(115200);
    while (!Serial) {};
	uint32_t old_mil = micros();
	count_sizes();
	sizes = (Size**)malloc(sizeof(Size*) * sizes_cnt);
	init_sizes(sizes);
	create_sizes(sp_incl);
    for (ii = 0; ii < Span_q; ii++) { minimum += spanners[ii].price; }
	begin_sort(sp_incl, sizes, minimum);
	minimum = minimum_find(sp_incl, sizes, minimum, 0);
	uint32_t tim = micros() - old_mil;
    print_spans(best_incl);
	Serial.print(F("Calculation time = "));
	Serial.print(tim/1000.0, 3);
	Serial.println(" ms");
}

void loop() {}

Результаты для кода выше (Ардуино ИДЕ 1.6.12):

Тестовый набор ЕП - 2.68 мс

Нфбор от Kolyn - 3.92 мс

Результаты для последних строчек урезанного набора ГОСТ ниже

{1, 2, 1}, // 2.5 x 3.2
{ 2, 4 , 2 }, // 3.2 x 4
{ 2, 3, 3 },  // 3.2 x 5.5
{ 4, 5, 4 },
{ 5, 3, 5 },  // 5 x 5.5
{ 3, 7, 6 },  // 5.5 x 7
{ 6, 7, 7 },
{ 7, 8, 8 }, 
{ 8, 9 , 41520 },
{ 8, 10, 43054 },
{ 9, 11, 9 },
{ 10, 11, 10 },
{ 10, 12, 51455 }, 
{ 10, 13, 11 },
{ 11, 12, 12 },
{ 11, 13, 13 },
{ 12, 13, 56544 },
{ 12, 14, 57675 }, 
{ 13, 14, 15 },
{ 13, 15, 62845 },
{ 13, 16, 16 },
{ 13, 17, 17 },
{ 14, 15, 61714 }, 
{ 14, 17, 70276 },
{ 16, 17, 76496 }, // не достаточно памяти
{ 16, 18, 81989 },  // 36.4 миллисекунд
{ 17, 19, 82312 },
{ 17, 22, 18 }, //  // 35.3 миллисекунд
{ 18, 19, 82877 },
{ 18, 21, 19 }, // 12.9 миллисекунд

Как видно, скорость работы зависит от числа ключей совсем не однозначно... Строчки выше тестировать не стал

Наборы из 100 ключей не работают.

Проверяйте

Есть еще вариант"Б" - медленный , зато более экономный до ресурсов. Его, если будет интерес, выложу позже. Но большой разницы там нет, например по ГОСТовскому набору максимум для варианта А - 30 ключей, для Б - 34, зато скорость ниже примерно в 5 раз

Моё виденье каким должен быть алгоритм, а вдруг ещё есть молчуны-участники и смогут осуществить за три дня:

1. Многоуровневая фильтрация массива ключей. (типа несколько уровней сито)
2. Если фильтрация не справилась, то перебор сочетаниями без повторений.

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

Или при грамотно продуманной  фильтрации перебор и не понадобиться.

Фильтрация:

1. Дубли с высокой ценой, при этом нужно учесть, что ключи могут быть перевёрнутыми, исключаются сразу.
2. Ключи, в которых размер встречается только один раз (уникальные ключи),  по любому добавляются в набор.
3. Тут проявляется условие, что у каждого ключа есть два размера не равных между собой. Т.е. на примере набора из задания, который я и буду приводить дальше, 6-8, 9-11, 24-27 уникальные ключи с размерами 6, 11, 27, а размеры 8, 9, 24 уже не нужны для дальнейшей проверки.
4. При этом ключ 8-9 уже не нужен, т.к. его размеры уже включены в результирующий набор.
5. Далее могут присутствовать ключи, у которых один размер исключен, можно сравнить его стоимость с остальными ключами с таким же размером и если его цена больше то исключить его. При этом, если кол-во ключей с этим размером был равен 2, то более дешёвый ключ становиться уникальным. А его второй размер исключается из дальнейшего перебора.
6. Потом можно в цикле повторить пункты 3-5.
7. Если что-то останется, то перебор сочетаний без повторений.

Виденье - это хорошо, а что сами не реализуете?

без 6 пункта уже реализовал, попробую за оставшееся время конкурса успеть.

Ну и 7 конечно.

касаемо вашей идеи насчет п 6, то далеко не в каждом наборе многократный проход дает выигрыш.
Я в сообщении 268 рисовал графы, в исходном наборе ваш п6 выгоден, а "кольцевом" мало что даст

Хотелось бы еще минимальных авторских комментариев к коду, желательно на "могучем". Патамушта не все могут уловить главную сюжетную линию;) Я - так точно;)))

Если есть конкретные вопросы, могу ответить. Правда, подробные комменты - только в понедельник, а то я с телефона

Смог сформулировать лишь общий - "как это работает?". Поэтому подожду.

Примерно, как описано у Андрея в 275, только в конце не перебор, а рекурсия на один шаг глубже и снова эти же 7 пунктов... И так пока граф ключей не кончится

Сегодняшние результаты:

Набор из задания - 18 миллисекунд

С добавлением к нему {9, 27, 71570} - 1902 миллисекунд

Набор от kolyn: 8 миллисекунд

До 30 ГОСТовских ключей -

    {1, 2 , 1}, // 2.5 x 3.2
    {2, 4 , 2}, // 3.2 x 4
    {2, 3, 3},  // 3.2 x 5.5
    {4, 5, 4}, 
    {5, 3, 5},  // 5 x 5.5
    {3, 7, 6},  // 5.5 x 7
    {6, 7, 7},
    {7, 8, 8},  // 1 миллисекунда
    {8, 9 , 41520},
    {8, 10, 43054},
    {9, 11, 9}, 
    {10, 11, 10},  
    {10, 12, 51455}, // 8 миллисекунд
    {10, 13, 11}, 
    {11, 12, 12},
    {11, 13, 13},
    {12, 13, 56544},
    {12, 14, 57675}, // 680 миллисекунд
    {13, 14, 15}, 
    {13, 15, 62845},
    {13, 16, 16}, 
    {13, 17, 17}, 
    {14, 15, 61714}, // 1230 миллисекунд
    {14, 17, 70276},
    {16, 17, 76496}, // 165978 миллисекунд
    {16, 18, 81989},
    {17, 19, 82312},
    {17, 22, 18}, // 78297 миллисекунд
    {18, 19, 82877},
    {18, 21, 19}, // 271453 миллисекунд

 

Ого, борьба обостряется :)

Может еще участники подтянутся? Еще есть порядка полутора суток :) - можно многое успеть.

Кстати, Евгений, по условиям конкурс закрывается в 0:00 час 1 декабря - по какому часовому поясу ? :)

Вроде правильно осуществил свой словесный алгоритм. Завтра (30 ноября) ещё потестирую с другими наборами и выложу код.

Набор из задания - 4 миллисекунд

С добавлением к нему {9, 27, 71570} - 1921 миллисекунд

Набор от kolyn: 8 миллисекунд

До 30 ГОСТовских ключей -

    {1, 2 , 1}, // 2.5 x 3.2
    {2, 4 , 2}, // 3.2 x 4
    {2, 3, 3},  // 3.2 x 5.5
    {4, 5, 4}, 
    {5, 3, 5},  // 5 x 5.5
    {3, 7, 6},  // 5.5 x 7
    {6, 7, 7},
    {7, 8, 8},  // 1 миллисекунда
    {8, 9 , 41520},
    {8, 10, 43054},
    {9, 11, 9}, 
    {10, 11, 10},  
    {10, 12, 51455}, // 2 миллисекуд
    {10, 13, 11}, 
    {11, 12, 12},
    {11, 13, 13},
    {12, 13, 56544},
    {12, 14, 57675}, // 76 миллисекунд
    {13, 14, 15}, 
    {13, 15, 62845},
    {13, 16, 16}, 
    {13, 17, 17}, 
    {14, 15, 61714}, // 79 миллисекунд
    {14, 17, 70276},
    {16, 17, 76496}, // 87587 миллисекунд
    {16, 18, 81989},  
    {17, 19, 82312},
    {17, 22, 18}, // 6197 миллисекунд
    {18, 19, 82877},
    {18, 21, 19}, // 83 миллисекунд

Ого, как "несимметрично" у вас... один ключ добавили и 500 раз разницы...

15 ключей и 12 размеров "улетели" в перебор.

Выкладываю окончательную версию. Завтра и компьютер включать не буду:)

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

  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},
    {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},
    //{9, 27, 71570}

};
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;            //ввели переменную кол-ва ключей, которые  включены "On" в набор
  uint8_t quantitySize = totalSize();//кол-во уникальных размеров и заодно удалили (excluded) дубли
  uint8_t minQuantSpann;            //ввели переменную миним. кол-во ключей, из которых может состоять набор
  if (quantitySize % 2 == 0)
    minQuantSpann = quantitySize / 2;
  else minQuantSpann = quantitySize / 2 + 1; //Вычислили мин. возможное кол-во ключей
  quantityOn = unique();                        //включили уникальные 6*8; 9*11; 24*27.
  exclud();                        //Тут исключать 8*9
  uint8_t quantitySizeOn =  onSize(quantityOn); //ввели переменную кол-ва размеров в "On" - ключах
  uint8_t arrBruteForce[quantitySize - quantitySizeOn] = {};
  arrey__B_F(quantityOff, quantityOn, arrBruteForce);
  //for (int k = 0; k < quantitySize - quantitySizeOn; k++){Serial.print(arrBruteForce[k]);Serial.print(',');}
  quantityOff = offSpanners();     //
  if (quantityOff == 0)return;
  sortOff(spanners); //Сортировка невклученных офф вперед
  //перебор вариантов.Почти все, что выше исключительно для умеьшения возм. сочетаний и времени.
  bruteForce(minQuantSpann, quantityOff, quantityOn, quantitySize,arrBruteForce, quantitySize - quantitySizeOn);
}

//
//  Функция печатает результирующий
//  набор ключей и его стоимость
//
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();
}
//--------------------------------------------------



//
// Функция пeребора вариантов сочетаний ключей
//
void  bruteForce(uint8_t minQ, uint8_t qOff, uint8_t qOn, uint8_t qSize,uint8_t *arr_B_F, uint8_t sizeA_B_F)
{
  uint8_t tempArr[qOff];
  uint32_t tempTotal = 4294967295;
  bool complectYes = false;

  for ( minQ; minQ <= qOff + qOn; minQ++)
  { //Serial.println(minQ);
    bool flagComplect = false;
    uint8_t *currArr;
    currArr = new uint8_t[minQ - qOn];


    for (uint8_t i = 0; i < minQ - qOn; i++)                     //первое сочетание ключей
    {
      currArr[i] = i ;
    }
    for (uint8_t i = 0; i < minQ - qOn; i++)                     //сделали их "on"
      spanners[currArr[i]].included = on;

    if (totalSizeOn1(arr_B_F, sizeA_B_F, currArr,  minQ,  qOn ) == true)                  //если собрался правильный набор набор
    {
      uint32_t currTotal = 0;
      for (uint8_t i = 0; i < minQ - qOn; i++)                   //подсчитали цену
      {
        currTotal += spanners[currArr[i]].price;
      }
      if (currTotal < tempTotal)                                 //если цена  меньше записанной или это первый набор
      {
        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;                            //записываем в темп аррей
        flagComplect = true;                                      //поднимаем флаг "собран комплект"

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

      
//Здесь начинается бред. Строки 135,136; 158,159; 178,179; 198,199
//в этом коде лишние, они тут просто не нужны
//Но если их закомментить, время выполнения УВЕЛИЧИВАЕТСЯ!!!


    while (NextSet(currArr, qOff-1, minQ - qOn))                     //новое сочетание ключей
    {
      uint32_t currTotal = 0;
      for (uint8_t i = 0; i < minQ - qOn; i++)                   //подсчитали цену
      {
        currTotal += spanners[currArr[i]].price;
      }
      if (currTotal >= tempTotal)                                //"граница" по цене
      {
        continue;
      }
      for (uint8_t i = 0; i < minQ - qOn; i++)                     //сделали их "on"
        spanners[currArr[i]].included = on;


     if (totalSizeOn1(arr_B_F, sizeA_B_F, currArr,  minQ,  qOn ) == true)                          //если собрался правильный набор набор
      {

        if  (currTotal < tempTotal )                              //если цена  меньше записанной или это первый набор
        {
          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;                           //записываем в темп аррей
          }
          flagComplect = true;                                     //поднимаем флаг "собран комплект"
        }
      }

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

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

    if (flagComplect == true)                                      // комплект был создан мин.1 раз
      complectYes = true;

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

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


//
//Функция вычисляет  количество существующих размеров среди включенных "On"ключей и сравнивает с кол-вом сущ. размеров
//
bool totalSizeOn1(uint8_t *arr_B_F, uint8_t sizeA_B_F, uint8_t *currA, uint8_t minQ, uint8_t qOn )
{
  uint8_t inSize = 0;
  for (uint8_t i = 0; i < sizeA_B_F; i++)
  {
    bool flag = false;

    for (uint8_t k = 0; k < minQ - qOn; k++)
    {
      if (arr_B_F[i] == spanners[currA[k]].size1 ||
          arr_B_F[i] == spanners[currA[k]].size2)
      {
        flag = true;
      }
    }
    if (flag) inSize++;
  }
  if (inSize != sizeA_B_F)
    return false;
  else return true;
}
//---------------------------------------------------------

//
//Функция всех сочетаний для чисел 1…n по m.
//Честно содрана на https://prog-cpp.ru/combinations/
//
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[] = {{0, 0, 0}};
  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++;
    }
  }
  //Serial.print(uniqueSpanner);
  return uniqueSpanner;

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

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

      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;
      }
    }

  }
  for (uint8_t i = 0; i < totalSpanners * 2; i++)
  {
    uint8_t j = 0;
    while (j < i && arrSize[j] != arrSize[i])
      ++j;

    if (j == i)
      inSize ++;
  }
  //Serial.print(inSize);

  return inSize;
}

//-------------------------------------------------------


//
//Функция вычисляет общее количество размеров в "он" ключах
//
uint8_t onSize(int8_t qOn)
{
  uint8_t arrSize[qOn * 2] = {};
  uint8_t inSize = 0;
  uint8_t y = 0;

  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    if (spanners[i].included == on)
    {
      arrSize[y] = spanners[i].size1;
      y++;
      arrSize[y] = spanners[i].size2;
      y++;
    }
  }

  for (uint8_t i = 0; i < qOn * 2; i++)
  {
    uint8_t j = 0;
    while (j < i && arrSize[j] != arrSize[i])
      ++j;

    if (j == i)
      inSize ++;
  }
  //Serial.print(inSize);

  return inSize;
}

//-------------------------------------------------------


void arrey__B_F(uint8_t qOff, uint8_t qOn, uint8_t *arrB_F)
{
  uint8_t arrOn[qOn * 2] = {};
  uint8_t arrSize[totalSpanners * 2] = {};
  uint8_t inSize = 0;
  uint8_t y = 0;
  uint8_t z = 0;
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    if (spanners[i].included == on)
    {
      arrOn[y] = spanners[i].size1;
      y++;
      arrOn[y] = spanners[i].size2;
      y++;
    }
    arrSize[z] = spanners[i].size1;
    z++;
    arrSize[z] = spanners[i].size2;
    z++;
  }
  for (uint8_t i = 0; i < totalSpanners * 2; i++)
  {
    uint8_t j = 0;
    while (j < i && arrSize[j] != arrSize[i])
      ++j;

    if (j == i)
    {
      bool flag = true;
     for (uint8_t k = 0; k < qOn * 2; k++)
        if (arrSize[i] == arrOn[k])
        {
          flag = false;
          
        }
      if (flag)
      {
        arrB_F[inSize] = arrSize[i];
        //Serial.print(inSize); Serial.print(',');
        inSize ++;
      }
    }
  }
}


//
// функция сортировки ключей от дешевых к дорогим
//
void spanSort(Spanner * spanarray)
{
  Spanner tmp[] = {{0, 0, 0}};
  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();
  const uint32_t duration = millis() - start;
  printResults();
  Serial.print("Время расчёта: ");
  Serial.print(duration);
  Serial.println(" миллисекунд");
}

void loop(void) {}

Набор из задания Время расчёта: 198 миллисекунд

 

Все тесты, которые я придумал или те корректные, что уже были ветке, у меня проходят

Строки 152-204 написал только сегодня, получилось коряво, ну раз работает не стал трогать.

Мой код:

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

Spanner(const uint8_t s1, const uint8_t s2, const uint32_t p, const bool ini = false) 
    :  price(p), size1(s1), size2(s2), included(ini) {}
  
  size_t printTo(Print & p) const {
    size_t res = p.print(size1);
    res += p.print(F("-"));
    res += p.print(size2);
    res += p.print(F(": "));
    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(F(" руб. "));
    res += p.print(priceCop % 100);
    res += p.print(F(" коп."));
    return res;
  }
};

//  Массив всех ключей
// Ключей в массиве не больше 100
// Размеры в одном ключе целочисленные, не равны 0, не равны между собой, и каждый не больше 255
// При наличии пресекающихся по размерам ключей в кол-ве больше 30 вычисления могут занять длительное время
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  sizes[totalSpanners * 2], cSizes[totalSpanners * 2];  

Spanner tempS[] = {{0,0,0,0}};
bool flag1=0, flag2=0, flag3=0; 
uint8_t totalSpanners1=0, allSizes=0;


// Функция перебора сочетаний без повторений
bool nextSet(uint8_t *indexKeys, int16_t n, int16_t m) {
  for (int16_t i = m - 1; i >= 0; i--) {
    if (indexKeys[i] < n - m + i) {
      indexKeys[i]++;
      for (int16_t j = i + 1; j < m; j++)
        indexKeys[j] = indexKeys[j - 1] + 1;
      return 1;
    }
  }
  return 0;
}

void doCalculations(void) {
  memset(sizes, 0, sizeof(sizes[0]) * (totalSpanners * 2)); // Обнуление массива размеров.
  memset(cSizes, 0, sizeof(cSizes[0]) * (totalSpanners * 2)); // Обнуление массива кол-ва одинаковых размеров.

  // Поиск более дорогих дублей и удаление их сдвигом из массива структур
  totalSpanners1 = totalSpanners;
  for (uint8_t i=0; i < totalSpanners1; i++) 
    for (uint8_t j=i+1; j < totalSpanners1; 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)))) {
        if (spanners[i].price >= spanners[j].price) {
          for (uint8_t k = i; k < totalSpanners1 - 1; k++)
            spanners[k] = spanners[k + 1];
          i--;
        } else {
          for (uint8_t k = j; k < totalSpanners1 - 1; k++)
            spanners[k] = spanners[k + 1];
          j--;
        }
      totalSpanners1--; 
      }

  // Если все дубли выводим результат с одним ключём
  if (totalSpanners1 == 1) {spanners[0].included = 1; return;}

  // Поиск всех размеров ключей и вычисление кол-ва каждого размера
  for (uint8_t i = 0; i < totalSpanners1; 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;
  }

  // Добавление ключей с одним размером в результирующий набор
  for (uint8_t i = 0; i < allSizes; i++) 
     if (cSizes[i] == 0)  
      for (uint8_t j=0; j < totalSpanners1; j++) { 
        if (spanners[j].included) continue;
          if (sizes[i] == spanners[j].size1 || sizes[i] == spanners[j].size2) 
            spanners[j].included = 1;
      }
        
  // Пометка вторых размеров из уже выбранных ключей на удаление
  for (uint8_t i=0; i < totalSpanners1; i++)
     if (spanners[i].included)
       for (uint8_t j = 0; j < allSizes; j++) 
         if (sizes[j] == spanners[i].size1 || sizes[j] == spanners[i].size2) cSizes[j] = 0;

  do {
    flag2=0;

    // Удаление размеров которые уже есть в выбраных ключах
    for (uint8_t i = 0; i < allSizes; i++)
      if (cSizes[i] == 0) {
        for (uint8_t j = i; j < allSizes - 1; j++) 
          {sizes[j] = sizes[j+1]; cSizes[j] = cSizes[j+1];}
        allSizes--; i--;
      }

    // Удаление ключей у которых оба размера совпадает с размерами уже выбранных ключей.
    for (uint8_t i = 0; i < totalSpanners1; i++) {
      if (spanners[i].included) continue;
      flag1=0;
      for (uint8_t j = 0; j < allSizes; j++)
        if (sizes[j] == spanners[i].size1 || sizes[j] == spanners[i].size2) flag1=1;
      if (!flag1) {
        for (uint8_t k = i; k < totalSpanners1 - 1; k++) 
          spanners[k] = spanners[k + 1];
        totalSpanners1--; i--;
        spanners[totalSpanners1].included = 0;
      }
    }

    // Удаляем более дорогие ключи с одним оставшимся размером, а если размера только два, второй ключ добовляем в результирующий набор, помечая размеры на удаление из этого ключа.
    for (uint8_t i = 0; i < allSizes; i++)
      for (uint8_t j = 0; j < totalSpanners1; j++) {
        if (spanners[j].included) continue;
        flag3=1;
        if (sizes[i] == spanners[j].size1) {
          for (uint8_t l = 0; l < allSizes; l++) 
            if (l != i) 
              if (sizes[l] == spanners[j].size2) {flag3=0; break;}
          if (flag3) {
            for (uint8_t k = 0; k < totalSpanners1; k++) {
              if (spanners[k].included) continue;
              if (k != j) 
                if (sizes[i] == spanners[k].size1 || sizes[i] == spanners[k].size2) 
                 if (spanners[j].price >=  spanners[k].price) {
                   if (cSizes[i] == 1) {
                     spanners[k].included = 1;
                     for (uint8_t o = 0; o < allSizes; o++)
                       if (sizes[o] == spanners[k].size1 || sizes[o] == spanners[k].size2) cSizes[o] = 0;
                  } else cSizes[i]--;
                  for (uint8_t o = j; o < totalSpanners1 - 1; o++) 
                    spanners[o] = spanners[o + 1];
                  totalSpanners1--; j--; flag2=1;
                  spanners[totalSpanners1].included = 0;
                  break;
                }
            }
          }
        }
        if (sizes[i] == spanners[j].size2) {          
          for (uint8_t l = 0; l < allSizes; l++) 
           if (l != i)
             if (sizes[l] == spanners[j].size1) {flag3=0; break;}
          if (flag3) {
            for (uint8_t k = 0; k < totalSpanners1; k++) {
              if (spanners[k].included) continue;
              if (k != j) 
                if (sizes[i] == spanners[k].size1 || sizes[i] == spanners[k].size2) 
                 if (spanners[j].price >=  spanners[k].price) {
                   if (cSizes[i] == 1) {
                     spanners[k].included = 1;
                     for (uint8_t o = 0; o < allSizes; o++)
                       if (sizes[o] == spanners[k].size1 || sizes[o] == spanners[k].size2) cSizes[o] = 0;
                  } else cSizes[i]--;
                  for (uint8_t o = j; o < totalSpanners1 - 1; o++) 
                    spanners[o] = spanners[o + 1];
                  totalSpanners1--; j--; flag2=1;
                  spanners[totalSpanners1].included = 0;
                  break;
                }
            }
          }     
        }  
      }
  } while (flag2);

  // Убираем уже выбранные ключи в конец массива
  for (uint8_t i = 0; i < totalSpanners1; i++)
    for (uint8_t j = 0; j < totalSpanners1 - 1; j++)
      if (spanners[j].included > spanners[j+1].included) {
        tempS[0] = spanners[j];
        spanners[j] = spanners[j + 1];
        spanners[j + 1] = tempS[0];
      }
  
  // Считаем оставшиеся ключи.
  for (uint8_t i = 0; i < totalSpanners1; i++)
    if (spanners[i].included == 1) totalSpanners1 = i;

  //Сортировка оставшихся ключей по цене от большей к меньшей
  for (uint8_t i = 0; i < totalSpanners1; i++)
    for (uint8_t j = 0; j < totalSpanners1 - 1; j++)
    if (spanners[j].price < spanners[j+1].price) {
      tempS[0] = spanners[j];
      spanners[j] = spanners[j + 1];
      spanners[j + 1] = tempS[0];
    }

  bool stopElem=0;
  int16_t n=totalSpanners1;
  uint8_t *indexKeys, rezIndexKeys[n], rezM=0, elem=0;
  indexKeys = new int8_t[n];
  uint64_t rezSumPrice = UINT64_MAX, sumPrice = 0;

  // перебор сочетаний индексов массива ключей
  // n - кол-во оставшихся не выбранных ключей
  // m - от половины оставшихся размеров до кол-ва не выбранных ключей
  for (int16_t m=round(((float)allSizes/2)); m <= n; m++) {
    for (int16_t i = 0; i < n; i++)
      indexKeys[i] = i;
    do {
      sumPrice = 0; flag1=1; 
      // Проверка, что сумма сочетания меньше суммы предыдущего выбранного сочетания
      for (int16_t i = 0; i < m; i++) {
        sumPrice = sumPrice + uint64_t(spanners[indexKeys[i]].price);
        if (sumPrice >= rezSumPrice) {flag1 = 0; break;}
      }
      if (flag1) {
        flag2=1;
        // Проверка наличия всех оставшихся размеров в сочетании
        for (uint8_t i=0; i < allSizes; i++) {
          for (uint8_t j=0; j < m; j++) {
            if ((spanners[indexKeys[j]].size1 == sizes[i]) ||  (spanners[indexKeys[j]].size2 == sizes[i])) break;
            if (j == m-1) 
              if ((spanners[indexKeys[j]].size1 != sizes[i]) &&  (spanners[indexKeys[j]].size2 != sizes[i]))
                flag2=0;
          }
          if (!flag2) break;
        }
      }
      // Если обе проверки пройдены сохраняем результат
      if (flag1 && flag2) {
        rezSumPrice = sumPrice;
        rezM = m;
        for (uint8_t j = 0; j < m; j++) 
          rezIndexKeys[j] = indexKeys[j];
      }
    } while (nextSet(indexKeys, n, m));
  } 
    // Добавляем ключи выбранные на основе перебора в результирующий набор
    for (uint8_t i = 0; i < rezM; i++) {
      spanners[rezIndexKeys[i]].included = 1;
    }
}

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

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

void loop(void) {}  

 

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

А можно два варианта на конкурс выложить? Второй не до конца проверенный.

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

Spanner(const uint8_t s1, const uint8_t s2, const uint32_t p, const bool ini = false) 
    :  price(p), size1(s1), size2(s2), included(ini) {}
  
  size_t printTo(Print & p) const {
    size_t res = p.print(size1);
    res += p.print(F("-"));
    res += p.print(size2);
    res += p.print(F(": "));
    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(F(" руб. "));
    res += p.print(priceCop % 100);
    res += p.print(F(" коп."));
    return res;
  }
};

//  Массив всех ключей
// Ключей в массиве не больше 100
// Размеры в одном ключе целочисленные, не равны 0, не равны между собой, и каждый не больше 255
// При наличии пресекающихся по размерам ключей в кол-ве больше 30 вычисления могут занять длительное время
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},
    {9, 27, 71570}

};
static constexpr uint8_t totalSpanners = sizeof(spanners) / sizeof(spanners[0]);

uint8_t  sizes[totalSpanners * 2], cSizes[totalSpanners * 2];  

Spanner tempS[] = {{0,0,0,0}};
bool flag1=0, flag2=0, flag3=0, flag4=0; 
uint8_t totalSpanners1=0, allSizes=0;


// Функция перебора сочетаний без повторений
bool nextSet(uint8_t *indexKeys, int16_t n, int16_t m) {
  for (int16_t i = m - 1; i >= 0; i--) {
    if (indexKeys[i] < n - m + i) {
      indexKeys[i]++;
      for (int16_t j = i + 1; j < m; j++)
        indexKeys[j] = indexKeys[j - 1] + 1;
      return 1;
    }
  }
  return 0;
}

void doCalculations(void) {
  // Поиск более дорогих дублей и удаление их сдвигом из массива структур
  totalSpanners1 = totalSpanners;
  for (uint8_t i=0; i < totalSpanners1; i++) 
    for (uint8_t j=i+1; j < totalSpanners1; 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)))) {
        if (spanners[i].price >= spanners[j].price) {
          for (uint8_t k = i; k < totalSpanners1 - 1; k++)
            spanners[k] = spanners[k + 1];
          i--;
        } else {
          for (uint8_t k = j; k < totalSpanners1 - 1; k++)
            spanners[k] = spanners[k + 1];
          j--;
        }
      totalSpanners1--; 
      }

  // Если все дубли выводим результат с одним ключём
  if (totalSpanners1 == 1) {spanners[0].included = 1; return;}
do {
  allSizes=0; flag1=0; flag2=0; flag3=0; flag4=0 ; 
  memset(sizes, 0, sizeof(sizes[0]) * (totalSpanners * 2)); // Обнуление массива размеров.
  memset(cSizes, 0, sizeof(cSizes[0]) * (totalSpanners * 2)); // Обнуление массива кол-ва одинаковых размеров.
  
  // Поиск всех размеров ключей и вычисление кол-ва каждого размера
  for (uint8_t i = 0; i < totalSpanners1; i++) {
    //if (!spanners[i].included) {
      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;
    //}
  }

  // Добавление ключей с одним размером в результирующий набор
  for (uint8_t i = 0; i < allSizes; i++) 
     if (cSizes[i] == 0)  
      for (uint8_t j=0; j < totalSpanners1; j++) { 
        if (spanners[j].included) continue;
          if (sizes[i] == spanners[j].size1 || sizes[i] == spanners[j].size2) 
            spanners[j].included = 1;
      }
        
  // Пометка вторых размеров из уже выбранных ключей на удаление
  for (uint8_t i=0; i < totalSpanners; i++)
     if (spanners[i].included)
       for (uint8_t j = 0; j < allSizes; j++) 
         if (sizes[j] == spanners[i].size1 || sizes[j] == spanners[i].size2) cSizes[j] = 0;

  do {
    flag2=0;

    // Удаление размеров которые уже есть в выбраных ключах
    for (uint8_t i = 0; i < allSizes; i++)
      if (cSizes[i] == 0) {
        for (uint8_t j = i; j < allSizes - 1; j++) 
          {sizes[j] = sizes[j+1]; cSizes[j] = cSizes[j+1];}
        allSizes--; i--;
      }

    // Удаление ключей у которых оба размера совпадает с размерами уже выбранных ключей.
    for (uint8_t i = 0; i < totalSpanners1; i++) {
      if (spanners[i].included) continue;
      flag1=0;
      for (uint8_t j = 0; j < allSizes; j++)
        if (sizes[j] == spanners[i].size1 || sizes[j] == spanners[i].size2) flag1=1;
      if (!flag1) {
        for (uint8_t k = i; k < totalSpanners - 1; k++) 
          spanners[k] = spanners[k + 1];
        totalSpanners1--; i--; flag4=1;
        spanners[totalSpanners].included = 0;
      }
    }

    // Удаляем более дорогие ключи с одним оставшимся размером, а если размера только два, второй ключ добовляем в результирующий набор, помечая размеры на удаление из этого ключа.
    for (uint8_t i = 0; i < allSizes; i++)
      for (uint8_t j = 0; j < totalSpanners1; j++) {
        if (spanners[j].included) continue;
        flag3=1;
        if (sizes[i] == spanners[j].size1) {
          for (uint8_t l = 0; l < allSizes; l++) 
            if (l != i) 
              if (sizes[l] == spanners[j].size2) {flag3=0; break;}
          if (flag3) {
            for (uint8_t k = 0; k < totalSpanners1; k++) {
              if (spanners[k].included) continue;
              if (k != j) 
                if (sizes[i] == spanners[k].size1 || sizes[i] == spanners[k].size2) 
                 if (spanners[j].price >=  spanners[k].price) {
                   if (cSizes[i] == 1) {
                     spanners[k].included = 1;
                     flag4=1;
                     for (uint8_t o = 0; o < allSizes; o++)
                       if (sizes[o] == spanners[k].size1 || sizes[o] == spanners[k].size2) cSizes[o] = 0; 
                  } else cSizes[i]--;
                  for (uint8_t o = j; o < totalSpanners - 1; o++) 
                    spanners[o] = spanners[o + 1];
                  totalSpanners1--; j--; flag2=1; flag4=1;
                  spanners[totalSpanners].included = 0;
                  break;
                }
            }
          }
        }
        if (sizes[i] == spanners[j].size2) {          
          for (uint8_t l = 0; l < allSizes; l++) 
           if (l != i)
             if (sizes[l] == spanners[j].size1) {flag3=0; break;}
          if (flag3) {
            for (uint8_t k = 0; k < totalSpanners1; k++) {
              if (spanners[k].included) continue;
              if (k != j) 
                if (sizes[i] == spanners[k].size1 || sizes[i] == spanners[k].size2) 
                 if (spanners[j].price >=  spanners[k].price) {
                   if (cSizes[i] == 1) {
                     spanners[k].included = 1;
                     flag4=1;
                     for (uint8_t o = 0; o < allSizes; o++)
                       if (sizes[o] == spanners[k].size1 || sizes[o] == spanners[k].size2) cSizes[o] = 0; 
                  } else cSizes[i]--;
                  for (uint8_t o = j; o < totalSpanners - 1; o++) 
                    spanners[o] = spanners[o + 1];
                  totalSpanners1--; j--; flag2=1; flag4=1;
                  spanners[totalSpanners].included = 0;
                  break;
                }
            }
          }     
        }  
      }
  } while (flag2);

  // Убираем уже выбранные ключи в конец массива
  for (uint8_t i = 0; i < totalSpanners1; i++)
    for (uint8_t j = 0; j < totalSpanners1 - 1; j++)
      if (spanners[j].included > spanners[j+1].included) {
        tempS[0] = spanners[j];
        spanners[j] = spanners[j + 1];
        spanners[j + 1] = tempS[0];
      }
  
  // Считаем оставшиеся ключи.
  for (uint8_t i = 0; i < totalSpanners1; i++)
    if (spanners[i].included == 1) totalSpanners1 = i;

} while (flag4);

  //Сортировка оставшихся ключей по цене от большей к меньшей
  for (uint8_t i = 0; i < totalSpanners1; i++)
    for (uint8_t j = 0; j < totalSpanners1 - 1; j++)
    if (spanners[j].price < spanners[j+1].price) {
      tempS[0] = spanners[j];
      spanners[j] = spanners[j + 1];
      spanners[j + 1] = tempS[0];
    }

  bool stopElem=0;
  int16_t n=totalSpanners1;
  uint8_t *indexKeys, rezIndexKeys[n], rezM=0, elem=0;
  indexKeys = new int8_t[n];
  uint64_t rezSumPrice = UINT64_MAX, sumPrice = 0;

  // перебор сочетаний индексов массива ключей
  // n - кол-во оставшихся не выбранных ключей
  // m - от половины оставшихся размеров до кол-ва не выбранных ключей
  for (int16_t m=round(((float)allSizes/2)); m <= n; m++) {
    for (int16_t i = 0; i < n; i++)
      indexKeys[i] = i;
    do {
      sumPrice = 0; flag1=1; 
      // Проверка, что сумма сочетания меньше суммы предыдущего выбранного сочетания
      for (int16_t i = 0; i < m; i++) {
        sumPrice = sumPrice + uint64_t(spanners[indexKeys[i]].price);
        if (sumPrice >= rezSumPrice) {flag1 = 0; break;}
      }
      if (flag1) {
        flag2=1;
        // Проверка наличия всех оставшихся размеров в сочетании
        for (uint8_t i=0; i < allSizes; i++) {
          for (uint8_t j=0; j < m; j++) {
            if ((spanners[indexKeys[j]].size1 == sizes[i]) ||  (spanners[indexKeys[j]].size2 == sizes[i])) break;
            if (j == m-1) 
              if ((spanners[indexKeys[j]].size1 != sizes[i]) &&  (spanners[indexKeys[j]].size2 != sizes[i]))
                flag2=0;
          }
          if (!flag2) break;
        }
      }
      // Если обе проверки пройдены сохраняем результат
      if (flag1 && flag2) {
        rezSumPrice = sumPrice;
        rezM = m;
        for (uint8_t j = 0; j < m; j++) 
          rezIndexKeys[j] = indexKeys[j];
      }
    } while (nextSet(indexKeys, n, m));
  } 
    // Добавляем ключи выбранные на основе перебора в результирующий набор
    for (uint8_t i = 0; i < rezM; i++) {
      spanners[rezIndexKeys[i]].included = 1;
    }
}

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

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

void loop(void) {}

Но результат с первым не сходиться. Где-то ошибка.

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

Немного подправил, но всё равно не то.

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

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

Spanner(const uint8_t s1, const uint8_t s2, const uint32_t p, const bool ini = false) 
    :  price(p), size1(s1), size2(s2), included(ini) {}
  
  size_t printTo(Print & p) const {
    size_t res = p.print(size1);
    res += p.print(F("-"));
    res += p.print(size2);
    res += p.print(F(": "));
    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(F(" руб. "));
    res += p.print(priceCop % 100);
    res += p.print(F(" коп."));
    return res;
  }
};

//  Массив всех ключей
// Ключей в массиве не больше 100
// Размеры в одном ключе целочисленные, не равны 0, не равны между собой, и каждый не больше 255
// При наличии пресекающихся по размерам ключей в кол-ве больше 30 вычисления могут занять длительное время
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},
//    {9, 27, 71570}

};
static constexpr uint8_t totalSpanners = sizeof(spanners) / sizeof(spanners[0]);

uint8_t  sizes[totalSpanners * 2], cSizes[totalSpanners * 2];  

Spanner tempS[] = {{0,0,0,0}};
bool flag1=0, flag2=0, flag3=0, flag4=0; 
uint8_t totalSpanners1=0, allSizes=0;


// Функция перебора сочетаний без повторений
bool nextSet(uint8_t *indexKeys, int16_t n, int16_t m) {
  for (int16_t i = m - 1; i >= 0; i--) {
    if (indexKeys[i] < n - m + i) {
      indexKeys[i]++;
      for (int16_t j = i + 1; j < m; j++)
        indexKeys[j] = indexKeys[j - 1] + 1;
      return 1;
    }
  }
  return 0;
}

void doCalculations(void) {
  // Поиск более дорогих дублей и удаление их сдвигом из массива структур
  totalSpanners1 = totalSpanners;
  for (uint8_t i=0; i < totalSpanners1; i++) 
    for (uint8_t j=i+1; j < totalSpanners1; 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)))) {
        if (spanners[i].price >= spanners[j].price) {
          for (uint8_t k = i; k < totalSpanners1 - 1; k++)
            spanners[k] = spanners[k + 1];
          i--;
        } else {
          for (uint8_t k = j; k < totalSpanners1 - 1; k++)
            spanners[k] = spanners[k + 1];
          j--;
        }
      totalSpanners1--; 
      }

  // Если все дубли выводим результат с одним ключём
  if (totalSpanners1 == 1) {spanners[0].included = 1; return;}
do {
  allSizes=0; flag1=0; flag2=0; flag3=0; flag4=0 ; 
  memset(sizes, 0, sizeof(sizes[0]) * (totalSpanners * 2)); // Обнуление массива размеров.
  memset(cSizes, 0, sizeof(cSizes[0]) * (totalSpanners * 2)); // Обнуление массива кол-ва одинаковых размеров.
  
  // Поиск всех размеров ключей и вычисление кол-ва каждого размера
  for (uint8_t i = 0; i < totalSpanners1; i++) {
    //if (!spanners[i].included) {
      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;
    //}
  }

  // Добавление ключей с одним размером в результирующий набор
  for (uint8_t i = 0; i < allSizes; i++) 
     if (cSizes[i] == 0)  
      for (uint8_t j=0; j < totalSpanners; j++) { 
        if (spanners[j].included) continue;
          if (sizes[i] == spanners[j].size1 || sizes[i] == spanners[j].size2) {
            spanners[j].included = 1; 
            flag4=1;
          }
      }
        
  // Пометка вторых размеров из уже выбранных ключей на удаление
  for (uint8_t i=0; i < totalSpanners; i++)
     if (spanners[i].included)
       for (uint8_t j = 0; j < allSizes; j++) 
         if (sizes[j] == spanners[i].size1 || sizes[j] == spanners[i].size2) cSizes[j] = 0;

  do {
    flag2=0;

    // Удаление размеров которые уже есть в выбраных ключах
    for (uint8_t i = 0; i < allSizes; i++)
      if (cSizes[i] == 0) {
        for (uint8_t j = i; j < allSizes - 1; j++) 
          {sizes[j] = sizes[j+1]; cSizes[j] = cSizes[j+1];}
        allSizes--; i--;
      }

    // Удаление ключей у которых оба размера совпадает с размерами уже выбранных ключей.
    for (uint8_t i = 0; i < totalSpanners1; i++) {
      if (spanners[i].included) continue;
      flag1=0;
      for (uint8_t j = 0; j < allSizes; j++)
        if (sizes[j] == spanners[i].size1 || sizes[j] == spanners[i].size2) flag1=1;
      if (!flag1) {
        for (uint8_t k = i; k < totalSpanners - 1; k++) 
          spanners[k] = spanners[k + 1];
        totalSpanners1--; i--; flag4=1;
        spanners[totalSpanners-1].included = 0;
      }
    }

    // Удаляем более дорогие ключи с одним оставшимся размером, а если размера только два, второй ключ добовляем в результирующий набор, помечая размеры на удаление из этого ключа.
    for (uint8_t i = 0; i < allSizes; i++)
      for (uint8_t j = 0; j < totalSpanners1; j++) {
        if (spanners[j].included) continue;
        flag3=1;
        if (sizes[i] == spanners[j].size1) {
          for (uint8_t l = 0; l < allSizes; l++) 
            if (l != i) 
              if (sizes[l] == spanners[j].size2) {flag3=0; break;}
          if (flag3) {
            for (uint8_t k = 0; k < totalSpanners1; k++) {
              if (spanners[k].included) continue;
              if (k != j) 
                if (sizes[i] == spanners[k].size1 || sizes[i] == spanners[k].size2) 
                 if (spanners[j].price >=  spanners[k].price) {
                   if (cSizes[i] == 1) {
                     spanners[k].included = 1;
                     flag4=1;
                     for (uint8_t o = 0; o < allSizes; o++)
                       if (sizes[o] == spanners[k].size1 || sizes[o] == spanners[k].size2) cSizes[o] = 0; 
                  } else cSizes[i]--;
                  for (uint8_t o = j; o < totalSpanners - 1; o++) 
                    spanners[o] = spanners[o + 1];
                  totalSpanners1--; j--; flag2=1; flag4=1;
                  spanners[totalSpanners-1].included = 0;
                  break;
                }
            }
          }
        }
        if (sizes[i] == spanners[j].size2) {          
          for (uint8_t l = 0; l < allSizes; l++) 
           if (l != i)
             if (sizes[l] == spanners[j].size1) {flag3=0; break;}
          if (flag3) {
            for (uint8_t k = 0; k < totalSpanners1; k++) {
              if (spanners[k].included) continue;
              if (k != j) 
                if (sizes[i] == spanners[k].size1 || sizes[i] == spanners[k].size2) 
                 if (spanners[j].price >=  spanners[k].price) {
                   if (cSizes[i] == 1) {
                     spanners[k].included = 1;
                     flag4=1;
                     for (uint8_t o = 0; o < allSizes; o++)
                       if (sizes[o] == spanners[k].size1 || sizes[o] == spanners[k].size2) cSizes[o] = 0; 
                  } else cSizes[i]--;
                  for (uint8_t o = j; o < totalSpanners - 1; o++) 
                    spanners[o] = spanners[o + 1];
                  totalSpanners1--; j--; flag2=1; flag4=1;
                  spanners[totalSpanners-1].included = 0;
                  break;
                }
            }
          }     
        }  
      }
  } while (flag2);

  // Убираем уже выбранные ключи в конец массива
  for (uint8_t i = 0; i < totalSpanners1; i++)
    for (uint8_t j = 0; j < totalSpanners1 - 1; j++)
      if (spanners[j].included > spanners[j+1].included) {
        tempS[0] = spanners[j];
        spanners[j] = spanners[j + 1];
        spanners[j + 1] = tempS[0];
      }
  
  // Считаем оставшиеся ключи.
  for (uint8_t i = 0; i < totalSpanners1; i++)
    if (spanners[i].included == 1) totalSpanners1 = i;

} while (flag4);

  //Сортировка оставшихся ключей по цене от большей к меньшей
  for (uint8_t i = 0; i < totalSpanners1; i++)
    for (uint8_t j = 0; j < totalSpanners1 - 1; j++)
    if (spanners[j].price < spanners[j+1].price) {
      tempS[0] = spanners[j];
      spanners[j] = spanners[j + 1];
      spanners[j + 1] = tempS[0];
    }

  bool stopElem=0;
  int16_t n=totalSpanners1;
  uint8_t *indexKeys, rezIndexKeys[n], rezM=0, elem=0;
  indexKeys = new int8_t[n];
  uint64_t rezSumPrice = UINT64_MAX, sumPrice = 0;

  // перебор сочетаний индексов массива ключей
  // n - кол-во оставшихся не выбранных ключей
  // m - от половины оставшихся размеров до кол-ва не выбранных ключей
  for (int16_t m=round(((float)allSizes/2)); m <= n; m++) {
    for (int16_t i = 0; i < n; i++)
      indexKeys[i] = i;
    do {
      sumPrice = 0; flag1=1; 
      // Проверка, что сумма сочетания меньше суммы предыдущего выбранного сочетания
      for (int16_t i = 0; i < m; i++) {
        sumPrice = sumPrice + uint64_t(spanners[indexKeys[i]].price);
        if (sumPrice >= rezSumPrice) {flag1 = 0; break;}
      }
      if (flag1) {
        flag2=1;
        // Проверка наличия всех оставшихся размеров в сочетании
        for (uint8_t i=0; i < allSizes; i++) {
          for (uint8_t j=0; j < m; j++) {
            if ((spanners[indexKeys[j]].size1 == sizes[i]) ||  (spanners[indexKeys[j]].size2 == sizes[i])) break;
            if (j == m-1) 
              if ((spanners[indexKeys[j]].size1 != sizes[i]) &&  (spanners[indexKeys[j]].size2 != sizes[i]))
                flag2=0;
          }
          if (!flag2) break;
        }
      }
      // Если обе проверки пройдены сохраняем результат
      if (flag1 && flag2) {
        rezSumPrice = sumPrice;
        rezM = m;
        for (uint8_t j = 0; j < m; j++) 
          rezIndexKeys[j] = indexKeys[j];
      }
    } while (nextSet(indexKeys, n, m));
  } 
    // Добавляем ключи выбранные на основе перебора в результирующий набор
    for (uint8_t i = 0; i < rezM; i++) {
      spanners[rezIndexKeys[i]].included = 1;
    }
}

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

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

void loop(void) {}  

Сравнение результатов с набором из задания:

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

Второй код:
Ключи
1. 8-10: 430 руб. 54 коп.
2. 12-13: 565 руб. 44 коп.
3. 14-15: 617 руб. 14 коп.
4. 6-8: 382 руб. 8 коп.
5. 9-11: 495 руб. 97 коп.
6. 14-17: 702 руб. 76 коп.
7. 16-18: 819 руб. 89 коп.
8. 19-22: 1108 руб. 26 коп.
9. 24-27: 1715 руб. 70 коп.
Стоимость набора: 6837 руб. 78 коп.
Время расчёта: 4 миллисекунд

 

Ну тут вроде очевидно все - во-втором наборе и ключей на один больше, и цена почти на 10%...

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

Андрей, Ваша оптимизация, изложенная в #275 и так работает достаточно эффективно. До пункта 5 сам не додумался, поэтому применять у себя не стал - ибо неспортивно:) Во всяком случае мое решение Вы переигрываете вчистую на большинстве тестовых наборов.

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

Тут ещё всё зависеть от наборов ЕвгенияП, правильности результатов всех этих наборов, отсутствие зацикливаний и что у нас по среднему получиться.

 

п 5 очень эффективный, да :) Особенно для "линейных" наборов ключей.  В исходном наборе Евгения п5 едва не позволяет найти оптимум чисто аналитическим путем, вообще без переборов :)

Я специально в #268 предложил "закольцевать" граф ключей, чтобы поиск минимума не был таким простым.

Конечно

На конкурс у меня только один рабочий и более менее шустрый - в сообщении #339.