1

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

13
  • А ограничения на N, M, Pi какие?
    – EzikBro
    25 апр 2021 в 19:04
  • Я же правильно понимаю, что это эвристический алгоритм? Нет. Это один из возможных вариантов реализации жадного алгоритма. нет идей как сделать это для неопределенного числа куч А вот это зачем? по заданию-то количество куч вполне себе определённое, и даже где-то заданное в условии.
    – Akina
    25 апр 2021 в 19:19
  • @Akina А для этой задачи жадный алгоритм работает? это же обычно надо доказывать?
    – Mikhajlo
    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 на количество куч.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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