さまざまなサイズのマテリアルのリストを含む配列があります: {4,3,4,1,7,8}. ただし、ビンはサイズ 10 までの材料を収容できます。配列内のすべての要素をパックするために必要なビンの最小数を調べる必要があります。
上記の配列の場合、3 つのビンにパックして、次のように分割でき{4,4,1}ます。3 本のストック パイプに収まる他の配置も考えられますが、それより少ない数では実行できません。{3,7}{8}
この問題をよりよく理解するために、再帰を通じてこの問題を解決しようとしています。
私はこのDP 処方を使用しています (pdf ファイルの 20 ページ)。
n = ∑nj 項目の入力 (n1;:::;nk) を考える
単一のビンにパックできる k-タプル (入力のサブセット) のセットを決定する
つまり、すべてのタプル (q1;:::; qk) の OPT(q1;:::;qk) = 1
このセットを Q で表す 各 k タプル q について、OPT(q) = 1
となる 再帰を使用して残りの値を計算する : OPT(i1;:: :;ik) = 1 + minOPT(i1 - q1;:::;ik - qk)
私はコードを作成しましたが、小さなデータセットでは問題なく動作します。しかし、配列のサイズを 6 要素以上に増やすと、非常に遅くなります。8 要素を含む配列を解くのに約 25 秒かかります。アルゴリズムに何か問題があるか教えていただけますか? 別の解決策は必要ありません---なぜこれが遅いのか、どうすれば改善できるのかを知りたいだけです
これが私が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);
}
}