Понимание суммы подмножеств

Question

Я только что начал изучать алгоритмы 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.

Логика, которую я пытаюсь следовать:

1. Возьмите в элементах основного SET в подмножество тех пор, пока сумма подмножество остается меньше или равно целевой сумме.
2. Если добавление определенного числа к сумме подмножества делает его больше, чем цель, оно не принимает его.
3. Как только он дойдет до конца комплекта, ответ не найден, он удаляет самое последнеенедавно принятое число из набора и начинает смотреть на цифры в позиции после удаления последнего номера. (с тех пор, как я храню в массиве '', это позиции выбранных номеров из основного SET).

Answer 1

решения, которые вы собираетесь найти, зависят от порядка записей в наборе из-за вашего «до тех пор, как» пункт в шаге 1.

Если принять записи до тех пор, как они надевают» t вы получите цель, как только вы сделали, например, «4» и «2», «8» перенесут вас на цель, так как до «8» «2» находится в вашем наборе, вы никогда не получите подмножество с «4» и «8».

Вы должны либо добавить возможность пропустить добавление записи (или добавить ее к одному подмножеству, но не другому), либо изменить порядок своего набора и пересмотреть его.

Answer 2

Могут быть, что стек свободного решения возможно, но обычно (и вообще самый простой!) Способ реализации отслеживания алгоритмов через рекурсию, например:

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 попадет в конце массива, он будет удалить последние из добавленных к частичному решению, и если это число было последнее число в массиве, оно снова запустится, чтобы удалить второе-последнее число из частичного решения. Он никогда не может зацикливаться более двух раз, потому что числа, включенные в частичное решение, находятся на разных позициях.

Answer 3

Я не анализировал алгоритм подробно, но меня поразило то, что в вашем алгоритме не учитывается вероятность того, что после того, как одно решение, которое начинается с числа X, может быть несколько решений, начиная с этого числа ,

Первым улучшением было бы избежать сброса вашего стека s и текущей суммы после того, как вы напечатали решение.