Вместо использования обратного отслеживания, вы рассматривали вместо этого использование алгоритма битовой маски? Я думаю, это сделает ваш алгоритм намного проще.
Вот схема того, как вы это сделаете:
Пусть N будет количеством элементов в вашем наборе. Таким образом, если набор равен {6,1,2,5}, тогда N будет равно 4. Пусть max_waste будет максимальным отходом, который мы можем устранить (10 в вашем примере).
int best = 0; // the best result so far
for (int mask = 1; mask <= (1<<N)-1; ++mask) {
// loop over each bit in the mask to see if it's set and add to the sum
int sm = 0;
for (int j = 0; j < N; ++j) {
if ( ((1<<j)&mask) != 0) {
// the bit is set, add this amount to the total
sm += your_set[j];
// possible optimization: if sm is greater than max waste, then break
// out of loop since there's no need to continue
}
}
// if sm <= max_waste, then see if this result produces a better one
// that our current best, and store accordingly
if (sm <= max_waste) {
best = max(max_waste - sm);
}
}
Этот алгоритм очень похож на возврат и имеет аналогичную сложность, он просто не использует рекурсию.
Битовая маска в основном является двоичным представлением, где 1 указывает, что мы используем элемент в наборе, а 0 означает, что мы не используем. Поскольку мы выполняем цикл от 1 до (1<<N)-1, мы рассматриваем все возможные подмножества данных элементов.
Обратите внимание, что время работы этого алгоритма увеличивается очень быстро по мере увеличения N, но при N <= около 20 все должно быть в порядке. Кстати, то же самое относится и к возврату. Если вам нужна более высокая производительность, вам нужно рассмотреть другой метод, такой как динамическое программирование. </p>
Для возврата вам нужно просто отслеживать, какой элемент в наборе вы используете, и вы либо пытаетесь использовать элемент, либо не использовать его. Если вы используете его, вы добавляете его к общей сумме, а если нет, вы переходите к следующему рекурсивному вызову без увеличения общей суммы. Затем вы уменьшаете итоговое значение (если вы увеличиваете его), и именно здесь начинается возврат.
Это очень похоже на описанный выше подход с битовой маской, и я предоставил решение для битовой маски, которое поможет вам лучше понять, как будет работать алгоритм обратного отслеживания.
EDIT
Хорошо, я не осознавал, что вы должны использовать рекурсию.
Hint1
Во-первых, я думаю, что вы можете значительно упростить свой код, просто используя одну рекурсивную функцию и поместив логику в эту функцию. Нет необходимости создавать все наборы заранее, а затем обрабатывать их (я не совсем уверен, что это то, что вы делаете, но, похоже, это так из вашего кода). Вы можете просто создать наборы, а затем отслеживать, где вы находитесь в наборе. Когда вы доберетесь до конца сета, посмотрите, лучше ли ваш результат.
Hint2
Если вам все еще нужны дополнительные подсказки, попробуйте подумать о том, что должна делать функция возврата. Каковы условия прекращения? Когда мы достигаем условия завершения, что нам нужно записать (например, получили ли мы новый лучший результат и т. Д.)?
Hint3
Оповещение о спойлере
Ниже приведена реализация C ++, чтобы дать вам некоторые идеи, поэтому перестаньте читать здесь, если вы хотите поработать над этим самостоятельно.
int bestDiff = 999999999;
int N;
vector< int > cur_items;
int cur_tot = 0;
int items[] = {6,1,2,5};
vector< int > best_items;
int max_waste;
void go(int at) {
if (cur_tot > max_waste)
// we've exceeded max_waste, so no need to continue
return;
if (at == N) {
// we're at the end of the input, see if we got a better result and
// if so, record it
if (max_waste - cur_tot < bestDiff) {
bestDiff = max_waste - cur_tot;
best_items = cur_items;
}
return;
}
// use this item
cur_items.push_back(items[at]);
cur_tot += items[at];
go(at+1);
// here's the backtracking part
cur_tot -= items[at];
cur_items.pop_back();
// don't use this item
go(at+1);
}
int main() {
// 4 items in the set, so N is 4
N=4;
// maximum waste we can eliminiate is 10
max_waste = 10;
// call the backtracking algo
go(0);
// output the results
cout<<"bestDiff = "<<bestDiff<<endl;
cout<<"The items are:"<<endl;
for (int i = 0; i < best_items.size(); ++i) {
cout<<best_items[i]<<" ";
}
return 0;
}