深度优先 + 双向搜索
双向搜索：将整个需要搜索的对象分成两半（在已知初态与终态的时候可以考虑）
感悟：首先可能会思考动态规划，但它的时间复杂度是（nv）v太大了，不适合。n比较小，可以考虑爆搜。然后这里有个非常好的技巧，就是把原数据分成两半，在通过一些技巧，剪枝，可以有效的降低时间复杂度。
本题思路
- 先搜索前 N / 2 的数据，枚举所有可能的重量集合，存入数组
- 对所有重量集合排序，从大到小（顺序优化），判重（排除冗余）
- 在搜索后一半，枚举所有可能的重量集合，然后当前集合X与前面的数组中一个集合Y，是得X+Y <= m，且X+Y是最大的
- 然后就是到枚举结束输出最大的X+Y
剪枝及优化
- 双向搜索的思路就大大降低了时间复杂度
- 对于从什么地方开始分开也有讲究：前一半的为 2(N/2) 后一半为 2(N/2)*o(二分)，所以可以中和下，可在 N/2 + 2 时分开
- 搜索顺序的优化： 从大到小
- 判重： STL 中的unique可以实现数组中的判重，也可以自己写一个不难
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;
}
