如何从固定列表中选择一系列数字，使它们的总和等于目标数字？

Question

如何从固定列表中选择一系列数字，使它们的总和等于目标数字？

3

假设我有一个目标数和一个可能的值列表，我可以从中选择创建一个序列，一旦选定每个数字后将它们相加，总和会等于目标：

target = 31
list = 2, 3, 4
possible sequence: 3 2 4 2 2 2 4 2 3 2 3 2

我希望：

首先确定是否有能够到达目标的序列。
返回其中一个（可能的）序列。

这是我的尝试：

#include <iostream>
#include <random>
#include <chrono>
#include <vector>

inline int GetRandomInt(int min = 0, int max = 1) {
    uint64_t timeSeed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
    std::seed_seq ss{ uint32_t(timeSeed & 0xffffffff), uint32_t(timeSeed >> 32) };
    std::mt19937_64 rng;
    rng.seed(ss);
    std::uniform_int_distribution<int> unif(min, max);

    return unif(rng);
}

void CreateSequence(int target, std::vector<int> &availableNumbers) {
    int numAttempts = 1;
    int count = 0;
    std::vector<int> elements;

    while (count != target) {
        while (count < target) {
            int elem = availableNumbers[GetRandomInt(0, availableNumbers.size() - 1)];

            count += elem;
            elements.push_back(elem);
        }

        if (count != target) {
            numAttempts++;
            count = 0;
            elements.clear();
        }
    }

    int size = elements.size();
    std::cout << "count: " << count << " | " << "num elements: " << size << " | " << "num attempts: " << numAttempts << std::endl;
    for (auto it = elements.begin(); it != elements.end(); it++) {
        std::cout << *it  << " ";
    }   
}

int main() {
    std::vector<int> availableNumbers = { 2, 3, 4 };

    CreateSequence(31, availableNumbers);
}

但是，如果数字列表不能恰当地达到这样的总和，则它可能无限循环; 例如：

std::vector<int> availableNumbers = { 3 };

CreateSequence(8, availableNumbers);

不存在任何连续三个数的和为8。此外，如果列表很大且目标数字很高，则可能会导致大量的处理（因为许多while检查失败）。

您将如何实现这种算法？

- markzzz

2

我在考虑 回溯 范式可能会有用：如果当前总和超过了目标，你可以放弃该分支并移动到另一个排列。 - ihavenoidea

这不就是找零问题吗？ - user58697

2个回答

0

如ihavenoidea所建议，我也会尝试回溯。此外，我还会按照降序排列数字，以加快处理速度。

注意：评论可能比答案更合适，但我被禁止发表评论。希望有所帮助。如果需要，我可以删除此答案。

- Damien

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Karl Zeilhofer · Accepted Answer

你提出的代码可能非常快，因为它是启发式的。但正如你所说，它有可能被困在一个几乎无限循环中。

如果想避免这种情况，你需要搜索完整的可能组合集。

抽象

让我们将算法定义为一个函数 f，具有标量目标 t 和向量 <b> 作为参数，返回系数向量 <c>，其中 <b> 和 <c> 具有相同的维度：
<c> = f(t, <b>)

首先，给定的数字集合 Sg 应该被缩小到它们的缩小集合 Sr，因此我们减少了解决方案向量 <c> 的维度。例如 {2,3,4,11} 可以缩小为 {2,3}。我们通过递归调用算法来实现这一点，通过将 Sg 分割成一个新目标 ti 和剩余数字作为新给定集合 Sgi，并询问算法是否找到任何解（非零向量）。如果是，从原始给定集合 Sg 中删除该目标 ti。重复这个过程直到不再找到任何解。

现在我们可以将这组数字看作一个多项式，其中我们正在寻找可能的系数 ci 来得到我们的目标 t。让我们将 Sb 中的每个元素称为 bi，其中 i={1..n}。

我们的测试总和 ts 是所有 i 的 ci * bi 的总和，其中每个 ci 可以从 0 运行到 ni = floor(t/bi)。

可能测试的数量 N 现在是所有 ni+1 的乘积：N = (n1+1) * (n2+1) * ... * (ni+1)。

现在通过将系数向量 <c> 表示为整数向量并递增 c1 并将溢出传递到向量中的下一个元素，重置 c1 等等来迭代所有可能性。

例子

#include <random>
#include <chrono>
#include <vector>
#include <iostream>

using namespace std;

static int evaluatePolynomial(const vector<int> &base, const vector<int> &coefficients)
{
    int v=0;
    for(unsigned long i=0; i<base.size(); i++){
        v += base[i]*coefficients[i];
    }
    return v;
}

static bool isZeroVector(vector<int> &v)
{
    for (auto it = v.begin(); it != v.end(); it++) {
        if(*it != 0){
            return false;
        }
    } 
    return true;
}

static vector<int> searchCoeffs(int target, vector<int> &set) {
    // TODO: reduce given set

    vector<int> n = set;
    vector<int> c = vector<int>(set.size(), 0);

    for(unsigned long int i=0; i<set.size(); i++){
        n[i] = target/set[i];
    }

    c[0] = 1;

    bool overflow = false;
    while(!overflow){
        if(evaluatePolynomial(set, c) == target){
            return c;
        }

        // increment coefficient vector
        overflow = true;
        for(unsigned long int i=0; i<c.size(); i++){
            c[i]++;
            if(c[i] > n[i]){
                c[i] = 0;
            }else{
                overflow = false;
                break;
            }
        }
    }
    return vector<int>(set.size(), 0);
}

static void print(int target, vector<int> &set, vector<int> &c)
{
    for(unsigned long i=0; i<set.size(); i++){
        for(int j=0; j<c[i]; j++){
            cout << set[i] << " ";
        }
    }
    cout << endl;

    cout << target << " = ";
    for(unsigned long i=0; i<set.size(); i++){
        cout << " +" << set[i] << "*" << c[i];
    }
    cout << endl;
}

int main() {
    vector<int> set = {4,3,2};
    int target = 31;

    auto c = searchCoeffs(target, set);
    print(target, set,c);
}

那段代码会打印出来。

4 4 4 4 4 4 4 3 
31 =  +4*7 +3*1 +2*0

进一步思考

高效的代码应该检测任何给定值中的零
如果已经超过目标值，则通过增加下一个系数来改进搜索。
当将c1设置为零时，可以计算目标值和评估多项式之间的差异，并检查该差异是否是b1的倍数，从而实现进一步加速。如果不是，则可以直接增加c2。
也许存在一些利用最小公倍数的快捷方式