Рекурсивная сумма подмножеств

Я прочитал некоторые другие обсуждения, но не могу понять, как исправить мою программу. Как это ни повторяется, мой счетчик индексов в конечном итоге становится слишком большим, и многообещающие не работают, так как он выходит за пределы (или, по крайней мере, я считаю, что это правильно). Как я могу исправить это так, чтобы индекс никогда не становился слишком большим?

vector<uint> w;                // vector of weights
vector<bool> include;
uint W;                        // the desired weight
uint index = 0;
uint weight = 0;               // the current weight of subsets
uint total = 0;                // superset total

void sum_of_subsets( uint index,
uint weight,
uint total,
vector<bool> &include,
vector<uint> &w,
uint W )
{
if( promising(index, weight, W, w, total) )
{
if( weight == W )
{
for( uint k = 0; k <= include.size(); k++ )
{
if(include.at(k))
cout << w.at(k) << " ";
}
}
else
{
include.at(index + 1) = 1;
sum_of_subsets( index + 1,
weight + w.at(index + 1 ),
total - w.at(index + 1),
include, w, W ) ;
include.at(index + 1) = 0;
sum_of_subsets( index + 1,
weight,
total - w.at(index + 1),
include, w, W );
}
}
}

bool promising ( uint index,
uint weight,
uint W,
vector<uint> w,
uint total )
{
return ( weight + total >= W )
&& ((weight == W) || (weight + w.at(index+1) <= W));
}

0

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]