Задача такая: Имеется N камней, известны их веса Pi (i=1...N), задано количество куч M. Требуется разложить камни на M куч так, чтобы минимизировать вес самой тяжелой кучи. Решала эту задачу таким способом: в кучу с наименьшим весом кладем самый тяжелый камень. Я же правильно понимаю, что это эвристический алгоритм? Мне нужно решить задачу именно перебором, но нет идей как сделать это для неопределенного числа куч.
-
А ограничения на N, M, Pi какие?– EzikBro25 апр 2021 в 19:04
-
Я же правильно понимаю, что это эвристический алгоритм? Нет. Это один из возможных вариантов реализации жадного алгоритма. нет идей как сделать это для неопределенного числа куч А вот это зачем? по заданию-то количество куч вполне себе определённое, и даже где-то заданное в условии.– Akina25 апр 2021 в 19:19
-
@Akina А для этой задачи жадный алгоритм работает? это же обычно надо доказывать?– Mikhailo26 апр 2021 в 5:40
-
А для этой задачи жадный алгоритм работает? Нет. Пример - 2 кучи, камни 2*3+3*2.– Akina26 апр 2021 в 5:49
-
В принципе это ни что иное как задача линейного раскроя (упрощённая версия задачи о рюкзаке) - т.е. чисто NP-полная задача, решаемая только полным перебором. Подход к решению может быть такой. Сперва из исходных данных считаем теоретически минимальный вес кучи. Тут же сравниваем его с наиболее тяжёлым камнем, если камень тяжелее - корректируем. Затем перебираем все варианты полного заполнения кучи, до посчитанного предела. Для каждого варианта берём оставшиеся камни и решаем подзадачу (рекурсивно).– Akina26 апр 2021 в 6:06
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
на количество куч.