1

Задача такая: Имеется N камней, известны их веса Pi (i=1...N), задано количество куч M. Требуется разложить камни на M куч так, чтобы минимизировать вес самой тяжелой кучи. Решала эту задачу таким способом: в кучу с наименьшим весом кладем самый тяжелый камень. Я же правильно понимаю, что это эвристический алгоритм? Мне нужно решить задачу именно перебором, но нет идей как сделать это для неопределенного числа куч.

12
  • А ограничения на N, M, Pi какие?
    – EzikBro
    25 апр 2021 в 19:04
  • Я же правильно понимаю, что это эвристический алгоритм? Нет. Это один из возможных вариантов реализации жадного алгоритма. нет идей как сделать это для неопределенного числа куч А вот это зачем? по заданию-то количество куч вполне себе определённое, и даже где-то заданное в условии.
    – Akina
    25 апр 2021 в 19:19
  • @Akina А для этой задачи жадный алгоритм работает? это же обычно надо доказывать?
    – Mikhailo
    26 апр 2021 в 5:40
  • А для этой задачи жадный алгоритм работает? Нет. Пример - 2 кучи, камни 2*3+3*2.
    – Akina
    26 апр 2021 в 5:49
  • В принципе это ни что иное как задача линейного раскроя (упрощённая версия задачи о рюкзаке) - т.е. чисто NP-полная задача, решаемая только полным перебором. Подход к решению может быть такой. Сперва из исходных данных считаем теоретически минимальный вес кучи. Тут же сравниваем его с наиболее тяжёлым камнем, если камень тяжелее - корректируем. Затем перебираем все варианты полного заполнения кучи, до посчитанного предела. Для каждого варианта берём оставшиеся камни и решаем подзадачу (рекурсивно).
    – Akina
    26 апр 2021 в 6:06

1 ответ 1

0

Перебор не самая эффективная стратегия решения задач, но если нужно решить перебором, то можно сделать это через рекурсию. Функция StoneBruteForce получает на вход:

iStone - номер текущего камня;

stoneWeights - вектор весов камней (Pi из условия задачи);

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

и возвращает вес самой тяжелой кучи и распределение камней по кучам в выходном аргументе answer:

    typedef double stone_weight;
    
    stone_weight StoneBruteForce(int iStone, const std::vector<stone_weight>& stoneWeights,
      std::vector<std::vector<stone_weight>>& heaps,
      std::vector<std::vector<stone_weight>>& answer)
    {
      stone_weight maxHeapWeight = numeric_limits<stone_weight>::max();
      if (iStone == stoneWeights.size() - 1)
      {
        //Последний камень - кладем его поочередно во все кучи, считаем их 
        //веса и запоминаем ответ, если вес самой тяжелой кучи меньше чем 
        //известный.
        for (std::vector<std::vector<stone_weight>>::iterator it = heaps.begin();
             it != heaps.end(); ++it)
        {
          it->push_back(stoneWeights[iStone]);
    
          //Посчитать веса всех куч и взять кучу с самым большим весом.
          stone_weight localMaxHeapWeight = 0.0;
          for (std::vector<std::vector<stone_weight>>::iterator itH = heaps.begin();
               itH != heaps.end(); ++itH)
          {
            stone_weight heapWeight = accumulate(itH->begin(), itH->end(), 0.0);
            if (heapWeight > localMaxHeapWeight)
              localMaxHeapWeight = heapWeight;
          }
    
          //Если самая тяжелая легче чем текущая самая тяжелая, запомним ее.
          if (maxHeapWeight > localMaxHeapWeight)
          {
            maxHeapWeight = localMaxHeapWeight;
            answer = heaps;
          }
          it->pop_back();
        }
      }
      else
      {
        //Не последний камень - кладем его поочередно во все кучи и продолжаем
        //рекурсию со следующим камнем.
        for (std::vector<std::vector<stone_weight>>::iterator it = heaps.begin();
             it != heaps.end(); ++it)
        {
          it->push_back(stoneWeights[iStone]);
          std::vector<std::vector<stone_weight>> localanswer;
          stone_weight localMaxHeapWeight = StoneBruteForce(iStone + 1, 
                                         stoneWeights, heaps, localanswer);
          if (maxHeapWeight > localMaxHeapWeight)
          {
            maxHeapWeight = localMaxHeapWeight;
            answer = localanswer;
          }
          it->pop_back();
        }
      }
      return maxHeapWeight;
    }
    
    void print_answer(stone_weight maxHeapWeight, 
                      std::vector<std::vector<stone_weight>>& answer)
    {
      int iHeap = 0;
      std::cout << "Max heap weight " << maxHeapWeight << std::endl;
      for (auto h : answer)
      {
        std::cout << "Heap " << iHeap << " stones";
        for (auto w : h)
          std::cout << " " << w;
        std::cout << std::endl;
        iHeap++;
      }
    }

Вызываем так

  std::vector<stone_weight> stoneWeights = { 1,2,3,4,5,6,7,8,9 };
  std::vector<std::vector<stone_weight>> heaps(3);
  stone_weight maxHeapWeight = StoneBruteForce(0, stoneWeights, heaps, answer);
  print_answer(minWeightDiff, answer);

Введенные пользователем веса камней надо положить в stoneWeights и изменить размер heaps на количество куч.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.