深度優(yōu)先 + 雙向搜索

雙向搜索：將整個需要搜索的對象分成兩半（在已知初態(tài)與終態(tài)的時候可以考慮）

原題鏈接

感悟：首先可能會思考動態(tài)規(guī)劃，但它的時間復雜度是（nv）v太大了，不適合。n比較小，可以考慮爆搜。然后這里有個非常好的技巧，就是把原數(shù)據(jù)分成兩半，在通過一些技巧，剪枝，可以有效的降低時間復雜度。

本題思路

1. 先搜索前 N / 2 的數(shù)據(jù)，枚舉所有可能的重量集合，存入數(shù)組
2. 對所有重量集合排序，從大到小（順序優(yōu)化），判重（排除冗余）
3. 在搜索后一半，枚舉所有可能的重量集合，然后當前集合X與前面的數(shù)組中一個集合Y，是得X+Y <= m，且X+Y是最大的
4. 然后就是到枚舉結束輸出最大的X+Y

剪枝及優(yōu)化

• 雙向搜索的思路就大大降低了時間復雜度
• 對于從什么地方開始分開也有講究：前一半的為 2^(N/2) 后一半為 2^(N/2)*o(二分)，所以可以中和下，可在 N/2 + 2 時分開
• 搜索順序的優(yōu)化： 從大到小
• 判重： STL 中的unique可以實現(xiàn)數(shù)組中的判重，也可以自己寫一個不難

ACcode

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;

int n, m, k;
int weights[1 << 24], g[50];
int cnt = 0, ans = 0;

void dfs_1(int u, int sum)
{
    if(u == k)
    {
        weights[cnt++] = sum;
        return;
    }
    
    if((LL)sum + g[u] <= m) dfs_1(u+1, sum+g[u]);
    dfs_1(u+1, sum);
}

void dfs_2(int u, int sum)
{
    if(u == n)
    {
        int l = 0, r = cnt -1;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(weights[mid] + (LL)sum <= m) l = mid;
            else r = mid - 1;
        }
        if(weights[l] + (LL)sum <= m) ans = max(ans, weights[l] + sum);
        return;
    }
    
    if(g[u] + (LL)sum <= m) dfs_2(u+1, g[u]+sum);
    dfs_2(u+1, sum);
}

int main()
{
    cin >> m >> n;
    for(int i = 0; i < n; i++) cin >> g[i];
    
    sort(g, g+n);
    reverse(g, g+n);
    
    k = n/2 + 2;
    dfs_1(0, 0);
    
    sort(weights, weights+cnt);
    int t = 1;
    for(int i = 1; i < cnt; i++)
        if(weights[i] != weights[i-1])
            weights[t++] = weights[i];
    cnt = t;
    
    dfs_2(k, 0);
    
    cout << ans << endl;
    
    return 0;
}