由于a^b==c，b^c==a，a^c==b是等价的，因此对于式子f[i]+f[j]+f[i^j]，是对称的。不妨我们认为f[i]>=f[j]>=f[i^j]
如果此前我们已经找到了一个值u=f[p]+f[q]+f[p^q]，而对于某个i，发现u>3*f[i]>=f[i]+f[j]+f[i^j]，那么在这个i上我们就没有必要再对j进行枚举，按照各个方法进行剪枝。
按照类似的思想，如果我们对f数组进行从大到小排序，如果发现u>f[i]+2*f[i]>=f[i]+f[j]+f[i^j]，那么由于f[j]右面的元素都比f[j]要小，那么剩下的j-n的元素也就没有必要考察了。

struct cood //储存位置以及数字
{
    int pos,num;
};

bool cmp(cood a, cood b) //按数字从大到小排序
{
    return a.num>b.num;
}
vector <cood>f;
int findit(vector <cood>f,int &p,int &q)//p q是要求的i j值，返回值是发生的比较次数
{
    int i,j,k,l=0,ans=0;
    vector <cood> g=f;
    sort(g.begin(),g.end(),cmp);
    for (i=0;i<f.size();i++)
        for (j=i;j<=f.size();j++)
        {
            ans++;
            k=g[i].num+g[j].num+g[j].num;
            if (k<=l) 
                break;
            k=g[i].num+g[j].num+f[g[i].pos ^ g[j].pos].num;
            if (k>l)
                l=k,p=g[i].pos,q=g[j].pos;
        }
    return ans;
}



该算法在产生随机数的情况下（n=4096，f[i]=rand()%4096），比较次数模拟如下：
5074
4124
4297
4445
4410
4378
4649
4160
4099
4308
4371
4174
4664
4380
4609
4278
4411
4678
4248
4213
平均复杂度大概是O(n)级别的，加上排序的O(nlog n)，总时间复杂度为O(nlog n)

以上是我的一点想法，不一定对，希望对你有所帮助

看过后深受启发，非常感谢！

[quote]由于a^b==c，b^c==a，a^c==b是等价的，因此对于式子f[i]+f[j]+f[i^j]，是对称的。不妨我们认为f[i]>=f[j]>=f[i^j]
如果此前我们已经找到了一个值u=f[p]+f[q]+f[p^q]，而对于某个i，发现u>3*f[i]>=f[i]+f[j]+f[i^j]，那么在这个i上我们就没有必要再对j进行枚举，按照各个方法进行剪枝。
按照类似的思想，如果我们对f数组进行从大到小排序，如果发现u>f[i]+2*f[i]>=f[i]+f[j]+f[i^j]，那么由于f[j]右面的元素都比f[j]要小，那么剩下的j-n的元素也就没有必要考察了。

struct cood //储存位置以及数字
{
    int pos,num;
};

bool cmp(cood a, cood b) //按数字从大到小排序
{
    return a.num>b.num;
}
vector <cood>f;
int findit(vector <cood>f,int &p,int &q)//p q是要求的i j值，返回值是发生的比较次数
{
    int i,j,k,l=0,ans=0;
    vector <cood> g=f;
    sort(g.begin(),g.end(),cmp);
    for (i=0;i<f.size();i++)
        for (j=i;j<=f.size();j++)
        {
            ans++;
            k=g[i].num+g[j].num+g[j].num;
            if (k<=l) 
                break;
            k=g[i].num+g[j].num+f[g[i].pos ^ g[j].pos].num;
            if (k>l)
                l=k,p=g[i].pos,q=g[j].pos;
        }
    return ans;
}



该算法在产生随机数的情况下（n=4096，f[i]=rand()%4096），比较次数模拟如下：
5074
4124
4297
4445
4410
4378
4649
4160
4099
4308
4371
4174
4664
4380
4609
4278
4411
4678
4248
4213
平均复杂度大概是O(n)级别的，加上排序的O(nlog n)，总时间复杂度为O(nlog n)

以上是我的一点想法，不一定对，希望对你有所帮助[/quote]

剪枝的效果确实比较好，但是问题扩展之后性能就比较差了，再搭车问问

这个问题是我做过简化，原问题是
对于一组线性无关的基(a1,a2,a3,a4,a5)，每个基ai都是[0,2^20)内的一个整数，则通过相互异或可以组合出31个互不相同的数(b1,...,b31)，求使得这31个数所对应的查表值之和最大的一组基

我按照类似的思想进行剪枝，貌似解空间还是有点大。后来求解了一下3维和4维的，发现求3个基速度相当快，求4个基速度就完全无法忍受了

不知道对于这种扩展的情况，是否还可以进一步剪枝？