У меня есть массив, который содержит список материалов разных размеров: {4,3,4,1,7,8}.Тем не менее, в мусорное ведро могут поместиться материалы до размера 10. Мне нужно выяснить минимальное количество бункеров, необходимое для упаковки всех элементов в массиве.
Для указанного выше массива вы можете упаковать 3 бункера и разделитьих следующим образом: {4,4,1}, {3,7}, {8}.Существуют и другие возможные способы, которые также подходят для трех стандартных труб, но это невозможно сделать с меньшим количеством
. Я пытаюсь решить эту проблему с помощью рекурсии, чтобы лучше ее понять.
Яиспользуя эту формулировку DP (стр. 20 файла pdf)
Рассмотрим ввод (n1; :::; nk) с n = ∑nj элементами
Определить наборk-кортежей (подмножеств входных данных), которые могут быть упакованы в один бин
То есть все кортежи (q1; :::; qk), для которых OPT (q1; :::; qk) = 1
Обозначим это множество через Q. Для каждого набора из q мы имеем OPT (q) = 1
Рассчитать оставшиеся значения, используя повторение: OPT (i1; :::; ik) = 1 + minOPT (i1 -q1; :::; ik - qk)
Я сделал код, и он отлично работает для небольшого набора данных.Но если увеличить размер моего массива до более чем 6 элементов, он станет чрезвычайно медленным - занимает около 25 секунд, чтобы решить массив, содержащий 8 элементов Можете ли вы сказать мне, если что-то не так с алгоритмом?Мне не нужно альтернативное решение --- просто нужно знать, почему это так медленно, и как его можно улучшить
Вот код, который я написал на C ++:
void recCutStock(Vector<int> & requests, int numStocks)
{
if (requests.size() == 0)
{
if(numStocks <= minSize)
{
minSize = numStocks;
}
// cout<<"GOT A RESULT : "<<numStocks<<endl;
return ;
}
else
{
if(numStocks+1 < minSize) //minSize is a global variable initialized with a big val
{
Vector<int> temp ; Vector<Vector<int> > posBins;
getBins(requests, temp, 0 , posBins); // 2-d array(stored in posBins) containing all possible single bin formations
for(int i =0; i < posBins.size(); i++)
{
Vector<int> subResult;
reqMinusPos(requests, subResult, posBins[i]); // subtracts the initial request array from the subArray
//displayArr(subResult);
recCutStock(subResult, numStocks+1);
}
}
else return;
}
}
Функция getBins выглядит следующим образом:
void getBins(Vector<int> & requests, Vector<int> current, int index, Vector<Vector<int> > & bins)
{
if (index == requests.size())
{
if(sum(current,requests) <= stockLength && sum(current, requests)>0 )
{
bins.add(current);
// printBins(current,requests);
}
return ;
}
else
{
getBins(requests, current, index+1 , bins);
current.add(index);
getBins(requests, current, index+1 , bins);
}
}