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

andriano
andriano аватар
Offline
Зарегистрирован: 20.06.2015

AndreyD пишет:

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

Это тоже правильный прием.

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

AndreyD пишет:

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

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

nik182
Offline
Зарегистрирован: 04.05.2015

b707 пишет:

AndreyD пишет:

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

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


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

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

nik182 пишет:
А в жизни как мне кажется ноль соответствует рожковому ключу у которого "рога" только с одной стороны. Есть у меня такие. Вот входят ли они в условие - это Евгений может сказать.

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

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

nik182][quote=b707 пишет:

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

В данном случае 0 это не размер ключа, а цифровая метка для размера ключа.

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

Немного оптимизировал код для "ветвей и границ", переписал узкие места, добавил больше входных проверок. В итоге время для тестового набора ЕП даже чуть выросло - было 2.8 мс, стало порядка 3.1мс. Зато время для набора kolyn из сообщения #173 уменьшилось почти вдвое - с 7.9мс до 4.1мс.

Код не выкладываю, потому что пока не могу справится с главной проблемой - нехваткой памяти. На невырожденных наборах более чем с 25-30 уникальными ключами глубина рекурсии, необходимой для решения, оказывается 5-6 уровней... память заканчивается и программа крашится...

 Думаю, что повысить этот предел в несколько раз у меня точно не выйдет, хорошо если удастся поднять на 30-50%. В связи с этим вопрос к ЕП - по условиям программа должна работать на "любом разумном числе ключей". Разумное в этой фразе - это сколько? :)

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016

на моей памяти максимальный размер рожковых ключей ограничивался 112 номером

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

ua6em пишет:

на моей памяти максимальный размер рожковых ключей ограничивался 112 номером

вопрос не о максимальном размере ключа, а о максимальном количестве ключей в наборе.

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016

b707 пишет:

ua6em пишет:

на моей памяти максимальный размер рожковых ключей ограничивался 112 номером

вопрос не о максимальном размере ключа, а о максимальном количестве ключей в наборе.

Гаечные ключи относятся к изделиям, размеры которых строго регламентированы ГОСТ и не могут быть нарушены...  от 3.3 мм до 155мм (39 размеров)

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

ua6em пишет:

Гаечные ключи относятся к изделиям, размеры которых строго регламентированы ГОСТ и не могут быть нарушены...  от 3.3 мм до 155мм (39 размеров)

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

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016

b707 пишет:

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

По ГОСТ 80 года если не ограничиваться рядами и ограничиться размером 80мм - 54 разных ключа (так устроит?)

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

ua6em пишет:

По ГОСТ 80 года если не ограничиваться рядами и ограничиться размером 80мм - 54 разных ключа (так устроит?)

нет

nik182
Offline
Зарегистрирован: 04.05.2015

ua6em пишет:

Гаечные ключи относятся к изделиям, размеры которых строго регламентированы ГОСТ и не могут быть нарушены...  от 3.3 мм до 155мм (39 размеров)

Вот на хрена ты влазишь в темы, в которых тебе нечего сказать по делу? Только свою глупость выносишь на люди. Информация по ГОСТ конечно интересная, но если бы ты поработал немножко головой, то вспомнил, что ключи бывают разные. На разных сторонах ключа могут быть разные типоразмеры, например 12-12 12-13 12-14, и тогда во сколько разных ключей превратятся 39 размеров? 

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016
static Spanner spanners[] = {
    {2.5, 3.2 , 1},
    {3.2, 4 , 2},
    {3.2, 5.5, 3},
    {4, 5, 4},
    {5, 5.5, 5},
    {5.5, 7, 6},
    {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},                                                     
};

 

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

b707 пишет:
Разумное в этой фразе - это сколько? :)

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

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016

kolyn! На этом наборе не взлетает:
 

//
//  Тип данных для хранения ключа
//
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[] = {
    {2.5, 3.2 , 1},
    {3.2, 4 , 2},
    {3.2, 5.5, 3},
    {4, 5, 4},
    {5, 5.5, 5},
    {5.5, 7, 6},
    {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}    
};
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="<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>" rel="nofollow"><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></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) {}

 

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

ua6em пишет:

kolyn! На этом наборе не взлетает:

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

Ты вот это

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

с тем что ты пытаешься задавать

static Spanner spanners[] = {
    {2.5, 3.2 , 1},
    {3.2, 4 , 2},
    {3.2, 5.5, 3},
    {4, 5, 4},
    {5, 5.5, 5},
    {5.5, 7, 6},

сравнивать не пробовал?

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

ua6em пишет:

kolyn! На этом наборе не взлетает:

Выше обсуждались цифровые метки, размеры можно немного переделать. Тогда корректный набор будет таким:

    {1, 2 , 1},
    {2, 4 , 2},
    {2, 3, 3},
    {4, 5, 4},
    {5, 3, 5},
    {3, 7, 6},
    {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} 

Ноль я не использовал, он мне отдельно нужен.

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

думаю, что переделывать этот набор смысла нет.

Не знаю, что тут будет с памятью, но решение этого набора методом перебора займет годы :)

Напомню,  совсем простенький набор kolyn из сообщения #173 потребовал на одной программе перебора порядка 3х минут, а на другой все 12... а сложность перебора с числом вариантов как растет? Факториал?

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

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016

поправил, код, канпилятор видимо сам в правильный формат данные ключей приводил )))
PS и чё тут еще не так?
 

//
//  Тип данных для хранения ключа
//
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[] = {
    {2, 3, 10000},
    {3, 4, 2},
    {3, 5, 3},
    {4, 5, 4},
    {5, 6, 5},
    {6, 7, 6},
    {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}    
};
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="<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>" rel="nofollow"><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></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) {}

 

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

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

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

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

b707 пишет:

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

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

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

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

ua6em пишет:

поправил, код, канпилятор видимо сам в правильный формат данные ключей приводил )))
PS и чё тут еще не так?
 

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

Экий Вы нетерпеливый. Это же полный перебор, Вам же писали выше - время пропорционально ФАКТОРИАЛУ от кол-ва ключей. Так что одно из двух - либо решит, либо у Вас электричество в розетке кончится:)

andriano
andriano аватар
Offline
Зарегистрирован: 20.06.2015

ua6em пишет:

Гаечные ключи относятся к изделиям, размеры которых строго регламентированы ГОСТ и не могут быть нарушены...  от 3.3 мм до 155мм (39 размеров)

Уточните, какой именно ГОСТ действует на Али.

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016

тогда надо менять алгоритм

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

ua6em пишет:

тогда надо менять алгоритм

Гэниально! 

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016

kolyn пишет:

ua6em пишет:

тогда надо менять алгоритм

Гэниально! 

на этом сайте только по пятницам приходят гениальные открытия )))

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

Надо ждать выступления AndreyD... очень заинтересовало, что там у него за алгоритм...

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

kolyn пишет:

Уж куда я этот здравый смысл не пытался приложить

Давайте, я попробую объяснить смысл метода.

Для начала напишем простой полный перебор. Выглядит он для N ключей вот так:

Solution current(0); // "Текущее решение" изначально пустое
Solution theBest(UINT32_MAX); // "Наилучшее" на данный момент решение. Изначально имеет огромную цену.

//
// При любом вызове эта функция перебирает
//     N-start вариантов
//
void britishMuseum(int start = 0) {
	for (int i = start; i < N; i++) {
		current.add(spanner[i]); // добавить i-ый ключ в текущее решение
		if (current.isCompleted()) { // ЕСЛИ текущее решения полное (все размеры есть)
			if (current.cheaper(theBest)) { // ЕСЛИ текущее решение дешевле наилучшего
				theBest = current;
			}
		}
		if (start + 1 < N) britishMuseum(start + 1); // здесь добавится следующий(ие) ключ(и)
                current.remove(spanner[i]); // удалим этот ключ
	}
}

// ВЫЗОВ
britishMuseum();

После такого вызова наилучшее решение останется theBest. При этом функция честно переберёт все N! вариантов решений.

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

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

//
//
void britishMuseum(int start = 0) {
	for (int i = start; i < N; i++) {
		current.add(spanner[i]); // добавить i-ый ключ в текущее решение
		if (current.isCompleted()) { // ЕСЛИ текущее решения полное (все размеры есть)
			if (current.cheaper(theBest)) { // ЕСЛИ текущее решение дешевле наилучшего
				theBest = current;
			}
		}
  		else if (start + 1 < N) britishMuseum(start + 1); // здесь добавится следующий(ие) ключ(и)
                current.remove(spanner[i]); // удалим этот ключ
	}
}

// ВЫЗОВ
britishMuseum();

Как видите, мы добавили единственное слово else в строке №11 и уже избавились от части рекурсивных вызовов.

Давайте думать дальше. А если мы заранее отсортируем массив ключей в порядке возрастания цены ключа? Тогда ведь мы сможем сделать вот что: как только цена текущего решения (пусть ещё неполного) сравнялась (или превысила) с ценой нашего наилучшего на данный момент решения, дальше можно не смотреть, т.к. цена решения будет только расти с добавлением каждого ключа, а значит, всё, что мы сможем получить на этой ветке заведомо будет хуже того решения, что у нас уже есть! Давайте это напишем:

Solution current(0); // "Текущее решение" изначально пустое
Solution theBest(UINT32_MAX); // "Наилучшее" на данный момент решение. Изначально имеет огромную цену.

//
// При любом вызове эта функция перебирает
//     N-start вариантов
//
void britishMuseum(int start = 0) {
	for (int i = start; i < N; i++) {
		current.add(spanner[i]); // добавить i-ый ключ в текущее решение
		if (current.cheaper(theBest)) { // ЕСЛИ текущее решение дешевле наилучшего
			if (current.isCompleted()) { // ЕСЛИ текущее решения полное (все размеры есть)
				theBest = current;
				current.remove(spanner[i]); // удалим этот ключ
				return; // Здесь больше нечего ловить
			}
		}
		else { // Ага, цена текущего решения достигла (превысила) лучшее на данный момент
			current.remove(spanner[i]); // удалим этот ключ
			return; // Здесь больше нечего ловить
		}
		if (start + 1 < N) britishMuseum(start + 1); // здесь добавится следующий(ие) ключ(и)
		current.remove(spanner[i]); // удалим этот ключ
	}
}

// ВЫЗОВ
britishMuseum();

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

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

Как видите, ничего сложного.

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

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

Как видите, ничего сложного.

Кажется не сложным, если дано решение, да еще с подробными комментариями :) У меня даже полный перебор с помощью рекурсии написать не получилось, вернее после 26-и ключей ломалось. Пришлось "сочетание без повторений" сколипастить и встраивать в код.

И если

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

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

на это еще соображалки хватило и в моем варианте решения применяется, то

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

 как только цена текущего решения (пусть ещё неполного) сравнялась (или превысила) с ценой нашего наилучшего на данный момент решения, дальше можно не смотреть

это уже никак не сложилось в целую картинку. Какие-то обрывки мелькали, когда разбирал задачу о рюкзаке, но то такое. В любом случае мое честное решение  в #150

 

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

kolyn пишет:

это уже никак не сложилось в целую картинку. 

До сих пор не сложилось или теперь уже устаканилось? А то в этом и есть вся фишка метода.

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

Сейчас, после Ваших пояснений

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

Как видите, ничего сложного.

 

Спасибо.

 

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016

b707 пишет:

Надо ждать выступления AndreyD... очень заинтересовало, что там у него за алгоритм...

Полный набор:
 

//
//  Массив КЛЮЧЕЙ ГАЕЧНЫХ С ОТКРЫТЫМ ЗЕВОМ ДВУСТОРОННИХ
//
static Spanner spanners[] = {
    {2, 3, 1}, // 2.5 x 3.2
    {3, 4, 2}, // 3.2 x 4
    {3, 5, 3}, // 3.2 x 5.5
    {4, 5, 4}, 
    {5, 6, 5}, // 5 x 5.5
    {5, 7, 6}, // 5.5 x 7
    {6, 7, 7},
    {7, 8, 8},        // за 2 миллисекунды   
      
    {8, 9 , 41520},
    {8, 10, 43054},
    {9, 11, 9}, 
    {10, 11, 10},            
    {10, 12, 51455},  // за 77 миллисекунд  
    
    {10, 13, 11}, 
    {11, 12, 12},
    {11, 13, 13},                   
    {12, 13, 56544},
    {12, 14, 57675},  // за 1835 миллисекунд

    {13, 14, 15},        
    {13, 15, 62845},
    {13, 16, 16}, 
    {13, 17, 17},   
    {14, 15, 61714},  // за 29400 миллисекунд

    {14, 17, 70276},
    {16, 17, 76496},
    {16, 18, 81989},
    {17, 19, 82312},    
    {17, 22, 18},     //  за 102724 миллисекунд
    
    {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},
    {85, 90, 40},
    {95, 100, 41}, 
    {105, 110, 42},
    {115, 120, 43},
    {120, 130, 44}, 
    {135, 145, 45}, 
    {150, 155, 46}  //       
};

 

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

Незачет. В строке 7 значение 5.5 описано как 5, а в строке 9 как 6

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

b707 пишет:
Незачет. В строке 7 значение 5.5 описано как 5, а в строке 9 как 6

Завидую белой завистью. Вот КАК на это можно было внимание обратить?

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

kolyn пишет:

КАК на это можно было внимание обратить?


специально искал

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016

kolyn пишет:

b707 пишет:
Незачет. В строке 7 значение 5.5 описано как 5, а в строке 9 как 6

Завидую белой завистью. Вот КАК на это можно было внимание обратить?

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

PPS время в миллисекундах это для твоего алгоритма

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

ua6em пишет:

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


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

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016

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

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

ua6em пишет:

время в миллисекундах это для твоего алгоритма


это которого алгоритма, из 154?

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016

b707 пишет:
ua6em пишет:

время в миллисекундах это для твоего алгоритма

это которого алгоритма, из 154?

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

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

ua6em пишет:

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


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

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

ua6em пишет:

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


она в ветке выкладывалась? В каком сообщении?

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016

b707 пишет:
ua6em пишет:

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

она в ветке выкладывалась? В каком сообщении?

пролистал, не нашёл, колян подскажет

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

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

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

Если речь о моем варианте - то #150 последнее, что выкладывал

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

b707 пишет:
Перебором там должно быть на несколько порядков больше.

Проверил, цифры до миллисекунд не сходятся, но порядок верный.  Время расчёта: 129867 миллисекунд против  {17, 22, 18},     //  за 102724 миллисекунд

 

Дело в том,что у меня не совсем "честный" перебор. Он начинается с  н-ключей, которые определяются по кол-ву размеров и заканчивается, если при добавлении очередного ключа не меняется мин. сумма.

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

Kolyn, Вам - верю. Тогда по числу ключей вы меня явно обходите. Мой алгоритм до 30 строчки не доберется.

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

b707 пишет:
Тогда по числу ключей вы меня явно обходите.

Это лишь потому, что что я рекурсию ниасилил;)

andriano
andriano аватар
Offline
Зарегистрирован: 20.06.2015

ua6em пишет:

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

(выделено мною)

Интересно, а какая цель была?

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

Так какова же была цель такого искажения?

ua6em
ua6em аватар
Онлайн
Зарегистрирован: 17.08.2016

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

да уж...полёт фантазии с утра...цифры реальные с монитора порта...почему у коляна несколько не те - не знаю...ядро минисоре оптимизация включена