此算法确实有效吗？子集回溯算法总和]]

Question

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

在教科书Foundations of Algorithms，第5 ^th

版中，其定义如下：

算法5.4：子集和问题的回溯算法

问题：给定[[n正整数（权重）和正整数W，确定总和为W的整数的所有组合。

Inputs：

正整数n，按以下顺序排序（不降序）的数组从1到n的正整数w以及正整数W。

Outputs：

总和为[[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);
}

按照我们的常规约定，

n，w，W，

和

include

不是输入我们的例程。如果这些变量是全局定义的，则对sum_of_subsets的顶级调用如下：sum_of_subsets(0, 0, total); [第5章末尾，exercise 13询问：

对子集总和问题使用回溯算法（算法5.4）查找以下总和为
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]);
到达此行时，您未正确回溯。

有人能够识别此算法有问题或实际编码以使其起作用吗？ 
我想知道这种回溯算法是否真的有效。在第五版教科书“基础算法”中，其定义如下：算法5.4：......>

Answer 1

pseudocode。在C ++中，数组始终从0开始。因此，当您尝试执行include[i+1]时，您可能会遇到问题，并且仅检查i < arraySize。