双向暴搜 + 剪枝 + 二分

本题采用双向暴搜, 使时间复杂度大大降低(具体降低多少,自己算去), 好啦现在开始上思路, 还有我踩的坑:

解题思路

首先, 本体有46个数据, 如果我们采用传统的暴搜(选或不选), 那么时间将会达到2^46, 所以肯定会TLE, 那么如果从头和尾一起搜呢, 从头搜一般需要2^23次, 从尾部搜需要2^23次,再将搜索头部的结果和搜索尾部的结果相互匹配最后找到最大值, 这个次数应该在2^24左右.
至于为啥用 n / 2 + 2,我不知道,y总说这样效率最高

那么有了这个思路接下来该怎么做呢?

剪枝

• 大于所能承受的重量,剪!
• 出现结果,剪!

二分

• 注意找到比小于搜索值的最大值就行了

暴搜+ 状态dp

• 选或不选

C++代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 50, M = (1 << 26) + 1;
long long n, m;
long long mx = 0;
long long a[M];
long long sum[M];
long long n_2 = 0;
//重载sort排序
bool cmp(long long i, long long j)
{
    return i > j;
}
//二分查找
void find(int u)
{
    int l = 0, r = n_2 - 1;
    long long x = m - u;
    while(l < r)
    {
        int mid = l + ((r - l + 1) >> 1);//向上取整
        if(sum[mid] <= x) l = mid;//查找结果小于或等于搜索值(x)
        else r = mid - 1;
    }
    mx = max(mx, sum[l] + u);
}
//从头部开始搜索
void dfs1(int j, long long u)
{
    if(j == n / 2 + 2)
    {
        sum[n_2] = u;//搜索到最深处, sum数组记录每个结果
        n_2++; 
        return ;
    }
    dfs1(j + 1, u);//不选
    if(a[j] + u <= m) dfs1(j + 1, u + a[j]);//合法,选
}
//从尾部开始搜索
void dfs2(int j, long long u)
{
    if(j == n)
    {
        //搜索完成,与头部搜索的结果匹配
        find(u);
        return ;
    }
    dfs2(j + 1, u);//不选
    if(sum[j] + u <= m) dfs2(j + 1, u + a[j]);//合法,选
}

int main()
{
    cin >> m >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n, cmp);
    dfs1(0, 0);
    //为了提过匹配过程的效率, 使用sort + unique 消除重复值
    sort(sum, sum + n_2);
    n_2 = unique(sum, sum + n_2) - sum;
    dfs2(n / 2 + 2, 0);
    cout << mx << endl;
    return 0;
}