Понимание суммы подмножеств
Я только начал учиться Backtracking алгоритмы в колледже. Каким-то образом мне удалось создать программу для задачи Subset-Sum. Работает нормально, но потом я обнаружил, что моя программа не выдает все возможные комбинации.
Например: целевая сумма может быть сотней комбинаций, но моя программа дает только 30.
Вот код Было бы очень полезно, если бы кто-то мог указать, в чем моя ошибка.
int tot=0;//tot is the total sum of all the numbers in the set.
int prob[500], d, s[100], top = -1, n; // n = number of elements in the set. prob[i] is the array with the set.
void subset()
{
int i=0,sum=0; //sum - being updated at every iteration and check if it matches 'd'
while(i<n)
{
if((sum+prob[i] <= d)&&(prob[i] <= d))
{
s[++top] = i;
sum+=prob[i];
}
if(sum == d) // d is the target sum
{
show(); // this function just displays the integer array 's'
top = -1; // top points to the recent number added to the int array 's'
i = s[top+1];
sum = 0;
}
i++;
while(i == n && top!=-1)
{
sum-=prob[s[top]];
i = s[top--]+1;
}
}
}
int main()
{
cout<<"Enter number of elements : ";cin>>n;
cout<<"Enter required sum : ";cin>>d;
cout<<"Enter SET :\n";
for(int i=0;i<n;i++)
{
cin>>prob[i];
tot+=prob[i];
}
if(d <= tot)
{
subset();
}
return 0;
}
Когда я запускаю программу:
Enter number of elements : 7
Enter the required sum : 12
Enter SET :
4 3 2 6 8 12 21
SOLUTION 1 : 4, 2, 6
SOLUTION 2 : 12
Хотя 4, 8 тоже решение, моя программа не показывает его.
Еще хуже с количеством входов 100 или более. Будет не менее 10000 комбинаций, но моя программа показывает 100.
Логика, которой я пытаюсь следовать:
- Возьмите элементы основного набора в подмножество, пока
сумма подмножества остается меньше или равна целевой сумме. - Если добавление определенного числа к сумме подмножества делает его
больше чем цель, это не берет это. - Как только он достигает конца
из набора, и ответ не был найден, он удаляет наиболее
недавно взятый номер из набора и начинает смотреть на номера
в позиции после позиции последнего номера удалены.
(так как то, что я храню в массиве ‘s’, это позиции
выбранные номера из основного набора).
Решение
Решения, которые вы найдете, зависят от порядка записей в наборе из-за вашего условия «как долго» на шаге 1.
Если вы принимаете заявки до тех пор, пока вы не достигнете цели, как только вы взяли, например, «4» и «2», «8» приведут вас к цели, поэтому, если «2» находится в вашем наборе до «8», вы никогда не получите подмножество с «4» и «8».
Вы должны либо добавить возможность пропустить добавление записи (или добавить ее в одно подмножество, но не в другое), либо изменить порядок своего набора и пересмотреть его.
Другие решения
Возможно, что решение без стека возможно, но обычный (и, как правило, самый простой!) Способ реализовать алгоритмы обратного отслеживания — это рекурсия, например:
int i = 0, n; // i needs to be visible to show()
int s[100];
// Considering only the subset of prob[] values whose indexes are >= start,
// print all subsets that sum to total.
void new_subsets(int start, int total) {
if (total == 0) show(); // total == 0 means we already have a solution
// Look for the next number that could fit
while (start < n && prob[start] > total) {
++start;
}
if (start < n) {
// We found a number, prob[start], that can be added without overflow.
// Try including it by solving the subproblem that results.
s[i++] = start;
new_subsets(start + 1, total - prob[start]);
i--;
// Now try excluding it by solving the subproblem that results.
new_subsets(start + 1, total);
}
}
Затем вы бы назвали это из main() с new_subsets(0, d);, Поначалу рекурсия может быть сложна для понимания, но важно обдумать ее — попробуйте решить более простые задачи (например, рекурсивно генерировать числа Фибоначчи), если вышеприведенное не имеет никакого смысла.
Вместо этого, работая с решением, которое вы дали, я вижу одну проблему: как только вы найдете решение, вы стираете его и начинаете искать новое решение с номера справа от первого числа, которое было включено в это решение (top = -1; i = s[top+1]; подразумевает i = s[0]и есть последующий i++;). Это будет пропустить решения, которые начинаются с того же первого номера. Вы должны просто сделать if (sum == d) { show(); } вместо этого, чтобы убедиться, что вы получите их все.
Я изначально нашел ваш внутренний while цикл довольно запутанный, но я думаю, что на самом деле все происходит правильно: однажды i дойдет до конца массива, он удалит последнее число, добавленное к частичному решению, и, если это число было последним числом в массиве, он снова зациклится, чтобы удалить второе до последнего число из частичного решения. Он никогда не может зацикливаться более двух раз, потому что числа, включенные в частичное решение, находятся в разных позициях.
Я не анализировал подробно алгоритм, но меня поразило то, что ваш алгоритм не учитывает вероятность того, что после одного решения, которое начинается с числа X, может быть несколько решений, начинающихся с этого числа.
Первым улучшением было бы избежать сброса стека s и промежуточная сумма после того, как вы напечатали решение.