0

我的问题有点难以解释，所以我会尽力而为。我正在编写一个程序，该程序将采用目标数字和其他数字列表。我希望它从列表中添加所有可能的数字组合，直到列表中的数字组合总和与目标数字相同。例如，如果目标数字是 6，并且提供的列表中有数字 <2, 3, 4, 5>，那么程序将打印 2+4=6 的解。

我目前的程序设置了 4 个嵌套循环，其中最外层的循环检查第一个数字为常量的组合。第二个循环保持第二个数字不变，其他两个也是如此。如果上述列表的目标数为 20，则程序将按以下方式检查：

2
2+3
2+3+4
2+3+4+5
2+3+5
2+4
2+4+5
2+5
3
3+4
3+4+5
3+5
4
4+5
5

然后它会返回一条消息说没有找到解决方案。这适用于小列表，但如果列表包含许多小数字并且目标数字很大，则效果不佳。由于程序只有四个循环，所以最多只能添加 4 个数字。

我不禁想到必须有更好的方法来做到这一点，因为对于更长的列表，唯一的解决方案是制作更多的嵌套循环，这是不切实际的。有没有办法在没有嵌套循环的情况下遍历数字列表的所有组合？

我希望这很容易理解。如果您想查看我的代码，请告诉我。谢谢您的帮助！

4

3 回答 3

0

我会从另一个方向接近这个....将列表中的所有数字加在一起，如果它不等于目标值，你就完成了....如果列表的添加大于目标，然后开始从列表的开头删除项目，直到与目标值匹配。如果您不匹配，（跳过目标值）并且附加值变得小于您的目标值，则适当处理该情况。

这应该只需要 1 个循环。

于 2013-11-10T11:46:52.423 回答
0

您可以将每个组合表示为N一位值，设置该元素是否应该在组合中。然后迭代所有组合相当于从 1 计数到 2 N，使用内部循环将对应于设置位的值相加。

如果设置大小为 64 或更少，那么您可以使用uint64_t循环计数器轻松完成此操作。如果它更大，那么无论如何你可能活不到足够长的时间来看到结果。

于 2013-11-10T13:42:13.210 回答
0

您可以使用这样的递归方法：

#include <iostream>
#include <vector>

using namespace std;

vector<bool> active_pos;
vector<int> input;

int recurse (int current_sum, int target_sum, int length) {
    if (length < 0) {
        return -1;
    }

    for (int i = 0; i < input.size(); i++) {
        if (active_pos[i]) {
            continue;
        }

        active_pos[i] = true;

        int tmp_sum = current_sum + input[i];


        if (tmp_sum == target_sum) {
            return tmp_sum;
        }

        int next_sum = recurse(tmp_sum, target_sum, length-1);
        if (next_sum == target_sum) {
            return next_sum;
        }

        active_pos[i] = false;
    }
    return -1;
}

int main(int argc, const char **argv) {
    input.push_back(2);
    input.push_back(3);
    input.push_back(4);
    input.push_back(5);
    input.push_back(6);

    int length = input.size();
    active_pos.resize(length);

    int res = recurse(0, 10, length);

    cout << "Result is: " << res << endl;
    cout << "Used numbers are: " <<  endl;
    for (int j = 0; j < length; j++) {
        if (active_pos[j]) {
            cout << input[j] << " ";
        }
    }
    cout << endl;
}

该函数调用自身并每次recurse()将参数减一。length一个向量跟踪已经采用的值。

如果 的实例recurse()找到匹配的总和，则返回该值。如果不是，则返回 -1。如果最终结果为 -1，则未找到匹配项。

于 2013-11-10T12:03:48.927 回答