ВНИМАНИЕ: Конкурс для начинающих!!!

kolyn
Offline
Зарегистрирован: 18.01.2019
Ключи
1. 2-8: 0 руб. 3 коп.
2. 1-8: 0 руб. 4 коп.
Стоимость набора: 0 руб. 7 коп.
Время расчёта: 0 миллисекунд

 

b707
Offline
Зарегистрирован: 26.05.2017

Сорри, там глюк был

вот такой набор:

static Spanner spanners[] = {
	{1, 8 , 0},
	{2, 8 , 3},
	{1, 2 , 0},
};

причем помоему тут ошибка не та же, что в тестах у Евгения

kolyn
Offline
Зарегистрирован: 18.01.2019

Бесплатных ключей быть не может согласно условия! Об этом думал.

 

 

b707
Offline
Зарегистрирован: 26.05.2017

kolyn пишет:

Бесплатных ключей быть не может согласно условия! Об этом думал.

что-то не вижу в головном сообщении таких ограничений. Пусть автор нас рассудит.

kolyn
Offline
Зарегистрирован: 18.01.2019

b707 пишет:

что-то не вижу в головном сообщении таких ограничений.

ЕвгенийП пишет:

Хочется купить самый дешёвый из возможных наборов ключей в котором были бы представлены ВСЁ размеры хотя бы по разу.

 

Купить .

AndreyD
Offline
Зарегистрирован: 07.10.2018

ЕвгенийП пишет:

AndreyD,

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

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

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

Исправил. Изменил строку 137.

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

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

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

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

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

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

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

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

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

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

void loop(void) {}  

 

b707
Offline
Зарегистрирован: 26.05.2017

kolyn пишет:

Купить .

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

А с точки зрения математики нуль должен работать точно так же, как любая другая цена.

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

Тем не менее слово за Евгением

kolyn
Offline
Зарегистрирован: 18.01.2019

b707 пишет:

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

Согласен. Но это прикладная задача.

ЕвгенийП пишет:

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

AndreyD
Offline
Зарегистрирован: 07.10.2018

b707 пишет:

что-то не вижу в головном сообщении таких ограничений. Пусть автор нас рассудит.

По условию у всех ключей есть цена, а 0 руб. это отсутствие цены. ИМХО.

b707
Offline
Зарегистрирован: 26.05.2017

kolyn, уточните, на какой плате получены Ваши результаты, приведенные в сообщении #65 ?

Просто у меня на стандартной Уно для Вашего кода тестовый набор из первого поста дает время 567 мс, а у вас написано 430

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

kolyn
Offline
Зарегистрирован: 18.01.2019

Нано 16 МГц Роботдин.

Перепроверил - 430

 

AndreyD
Offline
Зарегистрирован: 07.10.2018

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

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

AndreyD пишет:

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

на рободине:
 

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

LTO -disable, то программа компилируется, загружается, но НЕ РАБОТАЕТ

Скетч использует 6064 байт (18%) памяти устройства. Всего доступно 32256 байт.
Глобальные переменные используют 473 байт (23%) динамической памяти, оставляя 1575 байт для локальных переменных. Максимум: 2048 байт.

Пробовал, UNO, NANO, miniCore 328P - везде 534 миллисекунды

kolyn
Offline
Зарегистрирован: 18.01.2019

Достал лупу, осмотрел плату. Вроде кварц, не керамика. Написано JF16.000. Откуда такой огромный разброс?

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

kolyn пишет:

Достал лупу, осмотрел плату. Вроде кварц, не керамика. Написано JF16.000. Откуда такой огромный разброс?

какой бутлоадер? старый-новый?

kolyn
Offline
Зарегистрирован: 18.01.2019

ua6em пишет:

LTO -disable, то программа компилируется, загружается, но НЕ РАБОТАЕТ

Это что? Не нашел(

Optiboot

AndreyD
Offline
Зарегистрирован: 07.10.2018

Попробовал с optiboot загрузчиком такую же модельку нанки (первая была со старым загрузчиком) - 534.

b707
Offline
Зарегистрирован: 26.05.2017

kolyn пишет:

Откуда такой огромный разброс?

разные версии ядра Ардуино по разному компилируют. Пишите номер версии Ардуино ИДЕ

kolyn
Offline
Зарегистрирован: 18.01.2019

Завтра пойду мини из поделия выковыряю, проверю на ней. Единственное предположение - Нанку ронял, кусочек кварца отбил, частота повысилась. Но это скорее из области фантастики...

ИДЕ 1.8.7

AndreyD
Offline
Зарегистрирован: 07.10.2018

У меня 1.8.13 - windows

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

1.8.9 - Linux

у оптибута 7 релизов, интересно, какой именно?

kolyn
Offline
Зарегистрирован: 18.01.2019

Вопрос закрыт. Плата разогнана. Блинк за 811мс! Кварц, сцуко!

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

kolyn пишет:

Вопрос закрыт. Плата разогнана. Блинк за 811мс! Кварц, сцуко!

Геймер?

остался подвешенным вопрос, почему  в режиме компилятора LTO - disable  - не работает...

kolyn
Offline
Зарегистрирован: 18.01.2019

ua6em пишет:

Геймер?

остался подвешенным вопрос, почему  в режиме компилятора LTO - disable  - не работает...

Я не знаю что это((

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

kolyn пишет:

ua6em пишет:

Геймер?

остался подвешенным вопрос, почему  в режиме компилятора LTO - disable  - не работает...

Я не знаю что это((

Это оптимизатор, обычно наоборот, программы валятся при его включении )))

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

AndreyD пишет:
Исправил. Изменил строку 137.

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

Проблема в другом. Попробуйте, например, 60, ну или хотя бы 33 ключа с одинаковыми размерами. Цены могут быть и разными, но размеры у всех одинаковые. Запустите, посмотрите.

b707
Offline
Зарегистрирован: 26.05.2017

Евгений, как лрганизатор конкурса - рассудите спор. Могут быть  в наборе ключи с нулевой ценой или условия конкурса предполагают только ненулевые цены?

Спор и аргументы сторон - начная с сообщения #103

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Да, Вы же понимаете, что это, всё равно. Ну, если человек уже забился на то, что не могут, пусть не могут - дополним задачу таким условием.

AndreyD
Offline
Зарегистрирован: 07.10.2018

ЕвгенийП пишет:

Да, Вы же понимаете, что это, всё равно. Ну, если человек уже забился на то, что не могут, пусть не могут - дополним задачу таким условием.

А мой аргумент? http://arduino.ru/forum/pesochnitsa-razdel-dlya-novichkov/vnimanie-konku...

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

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

У его программы, кстати, есть ещё одна проблема явно не прописанная в условии. Программа не любит ключей с одинаковыми размерами на концах (а таких как раз в реальной жизни навалом - типа с одной стороны рожок, а с другой - храповик)! Но я про это помалкиваю - надо было в условии прописывать, а теперь нефиг :-)

kolyn
Offline
Зарегистрирован: 18.01.2019

ЕвгенийП пишет:

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

Это не баг, это фича!

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

kolyn пишет:

ЕвгенийП пишет:

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

Это не баг, это фича!

ага, и с LTO_disable не работает, какой то там еще секрет есть )))

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

kolyn пишет:

Это не баг, это фича!

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

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

kolyn,

Вы после вот этого выкладывали что-то? Я пропустил? Или пока еще нет?

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

AndreyD,

Вы попробовали вариант, о котором я писал? Проблема понятна?

kolyn
Offline
Зарегистрирован: 18.01.2019

ЕвгенийП пишет:

kolyn,

Вы после вот этого выкладывали что-то? Я пропустил? Или пока еще нет?

Нет пока, исправляю и перепроверяю еще раз. Вчера выяснилось, что время исполнения программы у меня и у других участников отличается на 20%. Думаю, что порчу память , и на разных версиях компилятора это по разному вылазит...

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

kolyn пишет:
Думаю, что порчу память
Так я же Вам писал, что портите.

kolyn
Offline
Зарегистрирован: 18.01.2019

ЕвгенийП пишет:

kolyn пишет:
Думаю, что порчу память
Так я же Вам писал, что портите.

Еще где-то...

 

AndreyD
Offline
Зарегистрирован: 07.10.2018

ЕвгенийП пишет:

AndreyD,

Вы попробовали вариант, о котором я писал? Проблема понятна?

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

А вот что получилось:

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

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

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

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

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

      for (uint8_t j=0; j < allSizes; j++) {
        if (sizes[j] == spanners[i].size1) {flag1=1; cSizes[j]++;}
        if (sizes[j] == spanners[i].size2) {flag2=1; cSizes[j]++;}
      }
        if (!flag1) {sizes[allSizes] = spanners[i].size1; allSizes++;} else flag1=0; 
        if (!flag2) {sizes[allSizes] = spanners[i].size2; allSizes++;} else flag2=0;
    }
    n = round(((float)allSizes/2)); // половина всех размеров, для рассчёта границы по кол-ву ключей в наборе

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

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

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

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

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

   // Основной цикл перебора
   do{  
     if (collection != 0) collection--;
     if (calc()) if ((total < rezTotal) || (rezTotal == 0)) {rezTotal = total; rezCollection=collection;}
  }while (collection>1); 
}

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

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

void loop(void) {}  

 

kolyn
Offline
Зарегистрирован: 18.01.2019

Евгений Петрович, давайте договоримся на берегу. Дано ключ 8*10 - 50руб. и  ключи 8*N и 10*N по 25руб.

Там еще куча ключей и в результат могут войти или 8*10 или 8*N и 10*N 

Если в ответе  8*N и 10*N  - ошибка или нет - цена то одинакова? В условии про минимальную сумму да, про мин кол-во нет.

И еще одно:

ЕвгенийП пишет:

Ну, вот, собственно, такая задача: имеется набор несимметричных ключей 

Так что точно не баг)). Там и без этого хватает тараканов.

AndreyD
Offline
Зарегистрирован: 07.10.2018

kolyn пишет:

Евгений Петрович, давайте договоримся на берегу. Дано ключ 8*10 - 50руб. и  ключи 8*N и 10*N по 25руб.

Я думаю вероятность того что ключи 8*N и 10*N будут равны по цене с точностью до копейки очень мала.

 

kolyn
Offline
Зарегистрирован: 18.01.2019

AndreyD пишет:

Я думаю вероятность того что ключи 8*N и 10*N будут равны по цене с точностью до копейки очень мала.

Тестовые комплекты хитрые будут, могут и такой придумать))

Как у тебя, ладится?

 

b707
Offline
Зарегистрирован: 26.05.2017

Я думаю любая комбинация цен допустима, в том числе и одинаковые цены. И если в условии сказано "минимальная цена" - то не важно, достигается ли она одним ключом 8х10 или двумя другими вполовину дешевле - минимум есть минимум.

AndreyD
Offline
Зарегистрирован: 07.10.2018

kolyn пишет:

AndreyD пишет:

Я думаю вероятность того что ключи 8*N и 10*N будут равны по цене с точностью до копейки очень мала.

Тестовые комплекты хитрые будут, могут и такой придумать))

Как у тебя, ладится?

Чуть выше выложил последний вариант.

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

kolyn
Offline
Зарегистрирован: 18.01.2019

Мои вариант с исправлениями. Учел даже ключи с "0-й" ценой. b707, теперь работает и с Вашим хитрым набором)). Но будет находить два дешевых вместо одного  при равной цене.


//
//  Тип данных для хранения ключа
//
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[] = {
  {1, 8 , 4},
  {2, 8 , 3},
  {4, 6 , 3},
  {12, 15 , 3},
  {2, 6 , 3},
  {4, 8 , 3},
  {6, 10 , 3}
};
static constexpr uint8_t totalSpanners = sizeof(spanners) / sizeof(spanners[0]);
const uint8_t on = 1, off = 0, excluded = 10;// если 1, то включается в результирующий набор,0 - возможно будет включен,10 - исключен из перебора

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

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



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

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

    for (uint8_t i = 0; i < minQ - qOn; i++)                     //первое сочетание ключей
    {
      currArr[i] = i + 1;
    }
    for (uint8_t i = 0; i < minQ - qOn; i++)                     //сделали их "on"
      spanners[currArr[i] - 1].included = on;
      
    if ( totalSizeOn(qOff, qOn, qSize) == true)                  //если собрался правильный набор набор
    {
      for (uint8_t i = 0; i < qOff + qOn; i++)                   //подсчитали цену
      {
        if (spanners[i].included == on)
          currTotal += spanners[i].price;
      }
      if ((currTotal <= tempTotal && tempTotal != ooo ) || tempTotal == ooo  )            //если цена  меньше записанной или это первый набор
      {
        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))                          //если собрался правильный набор набор
      {
        for (uint8_t i = 0; i < qOff + qOn; i++)                   //подсчитали цену
        {
          if (spanners[i].included == on)
            currTotal += spanners[i].price;
        }
        if ( (currTotal <= tempTotal && tempTotal != ooo )|| tempTotal == ooo  )            //если цена  меньше записанной или это первый набор
        {
          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="https://prog-cpp.ru/combinations/" rel="nofollow">https://prog-cpp.ru/combinations/</a>" rel="nofollow"><a href="https://prog-cpp.ru/combinations/" rel="nofollow">https://prog-cpp.ru/combinations/</a></a>
//
bool NextSet(uint8_t *a, uint8_t  n, uint8_t  m)
{
  uint8_t k = m;
  for (int i = k - 1; i >= 0; --i)
    if (a[i] < n - k + i + 1)
    {
      ++a[i];
      for (uint8_t j = i + 1; j < k; ++j)
        a[j] = a[j - 1] + 1;
      return true;
    }
  return false;
}
//-----------------------------------------------------

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

//
// функция сортировки ключей по "off"; ключи со значением included == off станут первыми
//
void sortOff(Spanner * spanarray)
{
  Spanner tmp[] = {{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) {}

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

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

Просьба, у кого есть возможность - проверьте у себя и сообщите время. 

Отдельно к ua6em: что там с оптимизатором?

 

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

kolyn пишет:

Евгений Петрович, давайте договоримся на берегу. Дано ключ 8*10 - 50руб. и  ключи 8*N и 10*N по 25руб.

Там еще куча ключей и в результат могут войти или 8*10 или 8*N и 10*N 

Если в ответе  8*N и 10*N  - ошибка или нет - цена то одинакова? 

 

А о чём тут договариваться? Ясно сказано, что в решении должны быть все размеры при минимальной цене. Никаких дополнительных условий по которым следует выбирать из двух и более решений с одинаковой ценой нет. Значит, подойдёт любое. Отбраковать решение можно только по одной из двух причин (или обеим сразу): 1) в нём не хватает какого-то размера и 2) существует более дешёвое решение. Других критериев нет.

AndreyD пишет:

Я думаю вероятность того что ключи 8*N и 10*N будут равны по цене с точностью до копейки очень мала.

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

AndreyD
Offline
Зарегистрирован: 07.10.2018

kolyn пишет:

Время расчёта: 641 миллисекунд

AndreyD
Offline
Зарегистрирован: 07.10.2018

Мой очередной вариант.

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

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

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

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

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

      for (uint8_t j=0; j < allSizes; j++) {
        if (sizes[j] == spanners[i].size1) {flag1=1; cSizes[j]++;}
        if (sizes[j] == spanners[i].size2) {flag2=1; cSizes[j]++;}
      }
        if (!flag1) {sizes[allSizes] = spanners[i].size1; allSizes++;} else flag1=0; 
        if (!flag2) {sizes[allSizes] = spanners[i].size2; allSizes++;} else flag2=0;
    }
    n = round(((float)allSizes/2)); // половина всех размеров, для рассчёта границы по кол-ву ключей в наборе

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

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

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

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

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

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

   // Основной цикл перебора
   do{  
     if (collection != 0) collection--;
     if (calc()) if ((total < rezTotal) || (rezTotal == 0)) {rezTotal = total; rezCollection=collection;}
  }while (collection>1); 
}

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

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

void loop(void) {}  

 

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

ЕвгенийП пишет:

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

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

kolyn
Offline
Зарегистрирован: 18.01.2019

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

//
//  Тип данных для хранения ключа
//
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; //Вычислили мин. возможное кол-во ключей
  //Serial.println(minQuantSpann);
  quantityOn = unique();                        //включили уникальные 6*8; 9*11; 24*27.
  exclud();                        //Тут исключать 8*9
  quantityOff = offSpanners();     //
  if (quantityOff == 0)return;
  sortOff(spanners); //Сортировка невклученных офф вперед
  //перебор вариантов.Почти все, что выше исключительно для умеьшения возм. сочетаний и времени.
  bruteForce(minQuantSpann, quantityOff, quantityOn, quantitySize);
}

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



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

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

    for (uint8_t i = 0; i < minQ - qOn; i++)                     //первое сочетание ключей
    {
      currArr[i] = i + 1;
    }
    for (uint8_t i = 0; i < minQ - qOn; i++)                     //сделали их "on"
      spanners[currArr[i] - 1].included = on;
      
    if ( totalSizeOn(qOff, qOn, qSize) == true)                  //если собрался правильный набор набор
    {
      for (uint8_t i = 0; i < qOff + qOn; i++)                   //подсчитали цену
      {
        if (spanners[i].included == on)
          currTotal += spanners[i].price;
      }
      if ((currTotal <= tempTotal && tempTotal != ooo ) || tempTotal == ooo  )            //если цена  меньше записанной или это первый набор
      {
        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))                          //если собрался правильный набор набор
      {
        for (uint8_t i = 0; i < qOff + qOn; i++)                   //подсчитали цену
        {
          if (spanners[i].included == on)
            currTotal += spanners[i].price;
        }
        if ( (currTotal <= tempTotal && tempTotal != ooo )|| tempTotal == ooo  )            //если цена  меньше записанной или это первый набор
        {
          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="https://prog-cpp.ru/combinations/" rel="nofollow">https://prog-cpp.ru/combinations/</a>" rel="nofollow"><a href="https://prog-cpp.ru/combinations/" rel="nofollow">https://prog-cpp.ru/combinations/</a></a>
//
bool NextSet(uint8_t *a, uint8_t  n, uint8_t  m)
{
  uint8_t k = m;
  for (int i = k - 1; i >= 0; --i)
    if (a[i] < n - k + i + 1)
    {
      ++a[i];
      for (uint8_t j = i + 1; j < k; ++j)
        a[j] = a[j - 1] + 1;
      return true;
    }
  return false;
}
//-----------------------------------------------------

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

//
// функция сортировки ключей по "off"; ключи со значением included == off станут первыми
//
void sortOff(Spanner * spanarray)
{
  Spanner tmp[] = {{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) {}

Время выполнения 516 миллисекунд.