Задача о куче камней. Перебор

Question

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

Answer 1

Перебор не самая эффективная стратегия решения задач, но если нужно решить перебором, то можно сделать это через рекурсию. Функция 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 на количество куч.

БЛОГ НА HUSL

Задача о куче камней. Перебор

Ответы (1 шт):