4

我刚开始Backtracking在大学学习算法。不知何故，我设法为子集和问题制作了一个程序。工作正常，但后来我发现我的程序并没有给出所有可能的组合。

例如：目标总和可能有一百个组合，但我的程序只给出 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. 一旦它到达集合的末尾，并且没有找到答案，它就会从集合中删除最近使用的数字，并开始查看最近删除的数字位置之后的位置中的数字。（因为我存储在数组's'中的是主SET中所选数字的位置）。
4

3 回答 3

1

可能有一个无堆栈的解决方案是可能的，但是实现回溯算法的通常（通常也是最简单的！）方法是通过递归，例如：

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()with调用它new_subsets(0, d);。递归一开始可能很难理解，但理解它很重要——如果上面没有任何意义，请尝试更简单的问题（例如递归生成斐波那契数）。

改为使用您给出的解决方案，我可以看到的一个问题是，一旦找到解决方案，您就会将其清除并开始从包含在此中的第一个数字右侧的数字中寻找新的解决方案解决方案（top = -1; i = s[top+1];暗示i = s[0]，并且有后续i++;）。这将错过以相同第一个数字开头的解决方案。你应该这样做if (sum == d) { show(); }，以确保你得到他们所有。

我最初发现您的内部while循环非常混乱，但我认为它实际上是在做正确的事情：一旦i到达数组的末尾，它将删除添加到部分解决方案中的最后一个数字，如果这个数字是数组中的最后一个数字，它将再次循环以从部分解决方案中删除倒数第二个数字。它永远不会循环超过两次，因为部分解决方案中包含的数字都在不同的位置。

于 2013-03-31T14:38:02.000 回答
1

由于步骤 1 中的“只要”子句，您要找到的解决方案取决于集合中条目的顺序。

如果你接受条目，只要它们没有让你超过目标，一旦你接受了例如'4'和'2'，'8'就会让你超过目标，只要'2'在你在'8'之前的集合，你永远不会得到'4'和'8'的子集。

您应该添加跳过添加条目的可能性（或将其添加到一个子集但不添加到另一个子集）或更改集合的顺序并重新检查它。

于 2013-03-31T12:47:10.067 回答
1

我没有详细分析算法，但让我印象深刻的是，你的算法没有考虑到这样一种可能性，即在有一个以数字 X 开头的解决方案之后，可能会有多个以该数字开头的解决方案。

第一个改进是避免s在打印解决方案后重置堆栈和运行总和。

于 2013-03-31T15:01:00.807 回答