主页 / 问题 / 1337131
Accepted
Learpcs
Asked:2022-03-11 15:54:31 +0000 UTC2022-03-11 15:54:31 +0000 UTC

蛮力任务没有及时通过 C++

  • 772

任务条件：

给定 N 个整数 X1, X2, ..., XN。需要在它们之间放置“+”和“-”符号，以便结果表达式的值等于给定的整数 S。

规范 输入第一行的输入文件 INPUT.TXT 包含数字 N 和 S。下一行包含 N 个数字，以空格分隔。限制：2≤N≤24，0≤Xi≤5*10^7，-10^9≤S≤10^9。

输出在输出文件 OUTPUT.TXT 中，如果不可能得到这样的结果，则输出“无解”，否则输出结果相等。如果解决方案不是唯一的，请打印任何一个。

好吧，我对这个问题的第一个想法是：N 很小，这意味着很有可能理清所有可能的符号排列情况。好吧，使用“周到的样子”的方法，你就可以理解，这里不可能想出一个贪心算法。所以我实现了一个完整的迭代：

#include<iostream>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;

string ans;

//функция генерации всех возможных сумм
void generate(const ll& need, ll sum_now, const vector<ll>& a, ll i, string str)
{
    if (i == a.size())
    {
        if (need == sum_now)
        {
            ans = str;
        }
    }
    if (i < a.size())
    {
        generate(need, sum_now + a[i], a, i + 1, str + "+" + to_string(a[i]));
        generate(need, sum_now - a[i], a, i + 1, str + "-" + to_string(a[i]));
    }
}

int main()
{
    ll n, s;
    cin >> n >> s;
    vector<ll> a(n);
    for (auto& x : a)
        cin >> x;
    
    //a[0] может быть только положительным, поэтому сразу вставляем его в сумму
    generate(s, a[0], a, 1, to_string(a[0])); 
    if (ans.empty())
        cout << "No solution" << endl;
    else
        cout << ans + "=" + to_string(s) << endl;
        
}

而这个决定并没有及时通过。而且还不完全清楚为什么。总共有 2^23 < 10^7 个搜索选项。理论上应该很快。有两个问题：

是否有可能以某种方式告诉程序立即结束所有递归调用并在找到正确答案时结束函数？当然，我有一个想法，你可以写return，但实际上我们只完成了1个调用？将包装这个版本这样做：

void generate(const ll& need, ll sum_now, const vector<ll>& a, ll i, string str)
{
    if (i == a.size())
    {
        if (need == sum_now)
        {
            ans = str;
            return;
        }
    }
    if (i < a.size())
    {
        generate(need, sum_now + a[i], a, i + 1, str + "+" + to_string(a[i]));
        generate(need, sum_now - a[i], a, i + 1, str + "-" + to_string(a[i]));
    }
}

自然，从理论上讲，这种优化不会有太大帮助，因为最长时间的工作仍然是是否应该显示“No solution”，这意味着枚举所有案例是不可避免的。如何优化我的算法？

问题出现了，这个问题是否有迭代解决方案，而不是递归解决方案？只是对他没有想法，如果你给我提示我会很高兴。

哈利的解决方案代码，也几乎通过了（见哈利的回答和评论）：

#include<iostream>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;

int main()
{
    ll n, s;
    cin >> n >> s;
    vector<ll> a(n);
    for (auto& x : a)
        cin >> x;
    int M = 1 << (n - 1);
    for (size_t i = 0; i < M; i++)
    {
        ll sum = a[0];
        int m = i;
        for (size_t j = 1; j < n; j++)
        {
            if (m & 1)
                sum += a[j];
            else
                sum -= a[j];
            m >>= 1;
        }
        if (sum == s)
        {
            cout << a[0];
            m = i;
            for (size_t j = 1; j < n; j++)
            {
                if (m & 1)
                    cout << "+" << a[j];
                else
                    cout << "-" << a[j];
                m >>= 1;
            }
            cout << "=" << s;
            return 0;
        }
    }
    cout << "No solution";
     
}
c++

2 个回答

  1. Best Answer

    在这里，一个完整的枚举，即使没有格雷......
    它完全符合时间。只是不需要任何线条！

    #include <vector>
#include <iostream>

using namespace std;


int main(int argc, char * argv[])
{
    vector<int> x;
    int N, S;
    cin >> N >> S;
    for(int i = 0; i < N; ++i)
    {
        int z;
        cin >> z;
        x.push_back(z);
    }
    unsigned int M = 1;
    M <<= N-1;
    for(unsigned int k = 0; k < M; ++k)
    {
        unsigned int m = k;
        int sum = x[0];
        for(int j = 1; j < N; ++j)
        {
            if (m&1) sum += x[j]; else sum -= x[j];
            m >>= 1;
        }
        if (sum == S)
        {
            m = k;
            cout << x[0];
            for(int j = 1; j < N; ++j)
            {
                if (m&1)
                {
                    cout << "+" << x[j];
                }
                else cout << "-" << x[j];
                m >>= 1;
            }
            cout << "=" << S << "\n";
            return 0;
        }
    }
    cout << "No solution\n";
}

    PS 通过运行写的，所以它没有优化并且带有某些“插件”......

    • 2

  2. 你做的一切都是正确的，除了两件事：你不必在搜索过程中为答案编写一个字符串。字符串操作涉及分配内存并在每次调用时复制它。

    您自己提到的第二个错误是在找到解决方案的那一刻没有正常停止。

    下面的代码通过返回搜索的成功/失败并在成功时分块打印答案来解决这两个困难：

    #include <iostream>

int x[25];

bool search(int i, int s) {
    if (i == 0) {
        if (x[0] == s) {
            std::cout << x[0];
            return true;
        }
        return false;
    }
    if (search(i - 1, s - x[i])) {
        std::cout << '+' << x[i];
        return true;
    }
    if (search(i - 1, s + x[i])) {
        std::cout << '-' << x[i];
        return true;
    }
    return false;
}

int main() {
    int n, s;
    std::cin >> n >> s;
    for (int i = 0; i < n; ++i) {
        std::cin >> x[i];
    }
    if (search(n - 1, s)) {
        std::cout << "=" << s << '\n';
    } else {
        std::cout << "No solution\n";
    }
}

    $ time echo -e "24 24\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1" | ./a.out 
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=24

real  0m0.002s
user  0m0.000s
sys   0m0.000s

$ time echo -e "24 25\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1" | ./a.out 
No solution

real  0m0.055s
user  0m0.052s
sys   0m0.004s

    PS问题说X_i整数。因此，可以有零值和负值。在这种情况下，我的程序打印得很奇怪：

    $ echo -e "2 0\n-1 -1" | ./a.out 
-1--1=0

$ echo -e "2 -2\n-1 -1" | ./a.out 
-1+-1=-2
    • 1

相关问题