c++ - 这个算法真的有效吗？子集总和回溯算法

Question

我想知道这个回溯算法是否真的有效。

课本中Foundations of Algorithms , 第 5 版，定义如下:

Algorithm 5.4: The Backtracking Algorithm for the Sum-of-Subsets Problem

Problem: Given n positive integers (weights) and a positive integer W, determine all combinations of the integers that sum up to W.

Inputs: positvie integer n, sorted (nondecreasing order) array of positive integers w indexed from 1 to n, and a positive integer W.

Outputs: all combinations of the integers that sum to W.

void sum_of_subsets(index i, 
                    int weight, int total)  {
  if (promising(i))
     if (weight == W)
        cout << include[1] through include [i];
     else {
        include[i + 1] = "yes";               // Include w[i + 1].
        sum_of_subsets(i + 1, weight + w[i + 1], total - w[i + 1]);
        include[i + 1] = "no";                // Do not include w[i + 1].
        sum_of_subsets(i + 1, weight, total - w[i + 1]);
     }
}

bool promising (index i);  {
  return (weight + total >= W) && (weight == W || weight + w[i + 1] <= W);
}

Following our usual convention, n, w, W, and include are not inputs to our routines. If these variables were defined globally, the top-level call to sum_of_subsets would be as follows:

sum_of_subsets(0, 0, total);

在第 5 章的末尾，exercise 13问:

13. Use the Backtracking algorithm for the Sum-of-Subsets problem (Algorithm 5.4) to find all combinations of the following numbers that sum to W = 52:

    w1 = 2     w2 = 10     w3 = 13     w4 = 17     w5 = 22     w6 = 42

我已经实现了这个精确的算法，计算从 1 开始的数组，但它不起作用...

 void sos(int i, int weight, int total) {
    int yes = 1;
    int no = 0;

    if (promising(i, weight, total)) {
        if (weight == W) {
            for (int j = 0; j < arraySize; j++) {
                std::cout << include[j] << " ";
            }
            std::cout << "\n";
        }
        else if(i < arraySize) {
            include[i+1] = yes;
            sos(i + 1, weight + w[i+1], total - w[i+1]);
            include[i+1] = no;
            sos(i + 1, weight, total - w[i+1]);
        }
    }
}


int promising(int i,  int weight, int total) {
    return (weight + total >= W) && (weight == W || weight + w[i+1] <= W);
}   

我认为问题出在这里:

sos(i + 1, weight, total - w[i+1]);
sum_of_subsets(i+1, weight, total-w[i+1]);

当您到达这条线时，您没有正确回溯。

是否有人能够识别此算法的问题或实际编写代码使其工作？

Answer 1

我个人认为算法有问题。没有边界检查，它使用了很多全局变量，并且假定数组是从 1 开始索引的。我不认为你可以逐字复制它。它是用于实际实现的伪代码。在 C++ 中，数组总是从 0 开始。因此，当您尝试执行 include[i+1] 时，您可能会遇到问题。而你只检查 i < arraySize .

该算法还假设您有一个名为 total 的全局变量, 由函数 promising 使用.

我对代码做了一些修改，把它放在一个类中，并稍微简化了它:

class Solution
{
private:
    vector<int> w;
    vector<int> include;

public:
    Solution(vector<int> weights) : w(std::move(weights)),
        include(w.size(), 0) {}

    void sos(int i, int weight, int total) {
        int yes = 1;
        int no = 0;
        int arraySize = include.size();

        if (weight == total) {
            for (int j = 0; j < arraySize; j++) {
                if (include[j]) {
                    std::cout << w[j] << " ";
                }
            }
            std::cout << "\n";
        }
        else if (i < arraySize)
        {
            include[i] = yes;
            //Include this weight
            sos(i + 1, weight + w[i], total);
            include[i] = no;
            //Exclude this weight
            sos(i + 1, weight, total);
        }
    }
};

int main()
{   
    Solution solution({ 2, 10, 13, 17, 22, 42 });
    solution.sos(0, 0, 52);
    //prints:    10 42
    //           13 17 22
}