|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 48; // 1≤N≤46
|
|
|
|
|
|
// 双向DFS
|
|
|
int n; // n个礼物
|
|
|
int m; // 重量之和不超过m,上限
|
|
|
int k; // 前k个，即索引下标0~k-1
|
|
|
int w[N]; // 每个礼物的重量
|
|
|
|
|
|
// 前半部分收集到的所有和,下标因为一直在保持++状态，所以最后一次执行完，也可以理解为前半部分数组的个数
|
|
|
// 在排序去重后，此变更也可以视为前半段数组的元素个数，在二分中，因为需要使用的是索引号：0~idx-1
|
|
|
int sum[1 << (N / 2)], idx; // Q:为什么这个数据范围需要开1<<(N/2)? 答：因为算一半，每个数字都可以有选或不选两个选择，就是2^23方
|
|
|
int ans; // 最大重量
|
|
|
|
|
|
// u:第几号礼物，下标从0开始
|
|
|
// s:本路线上累加的礼物物理和
|
|
|
void dfs1(int u, int s) {
|
|
|
if (u == k) { // 如果能够到达第k个下标位置，表示前面0~k-1共k个选择完毕
|
|
|
sum[idx++] = s; // 记录礼物重量和
|
|
|
return;
|
|
|
}
|
|
|
// 如果加上u号物品重量，不会超过上限m，那么可以选择
|
|
|
// 技巧：为防止两个int相加爆int,同时不想使用long long,可以考虑使用减法
|
|
|
if (s <= m - w[u]) dfs1(u + 1, s + w[u]);
|
|
|
// 放弃u号物品,走到下一个u+1号面前
|
|
|
dfs1(u + 1, s);
|
|
|
}
|
|
|
|
|
|
// 后半部分
|
|
|
void dfs2(int u, int s) {
|
|
|
if (u == n) {
|
|
|
// 目标:在一个从小到大的有序数组中，找到 小于等于某个数 的最大值
|
|
|
int l = 0, r = idx; //[左闭右开)
|
|
|
while (l < r) {
|
|
|
int mid = (l + r) >> 1;
|
|
|
if (sum[mid] > m - s)
|
|
|
r = mid;
|
|
|
else
|
|
|
l = mid + 1;
|
|
|
}
|
|
|
l--; // l是第一个大于目标值的位置，我们要找的是小于等于目标值的位置，l-1就是答案
|
|
|
|
|
|
// 更新更大重量
|
|
|
ans = max(ans, sum[l] + s);
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
// 如果加上u号物品重量，不会超过上限m，可以选择
|
|
|
if (s <= m - w[u]) dfs2(u + 1, s + w[u]);
|
|
|
|
|
|
// 放弃当前礼物
|
|
|
dfs2(u + 1, s);
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
scanf("%d %d", &m, &n); // 先读入m再读入n,别整反了
|
|
|
for (int i = 0; i < n; i++) scanf("%d", &w[i]); // 每个礼物重量
|
|
|
|
|
|
// 由大到小排序,搜索范围会小
|
|
|
// sort(w, w + n, greater<int>());
|
|
|
sort(w, w + n), reverse(w, w + n);
|
|
|
|
|
|
// 一家一半
|
|
|
k = n / 2;
|
|
|
|
|
|
// 前面开始搜索 0~k-1
|
|
|
// dfs1，枚举出了所有可能出现的组合值
|
|
|
dfs1(0, 0);
|
|
|
|
|
|
// 前半部重量累加结果由小到大排序
|
|
|
sort(sum, sum + idx);
|
|
|
|
|
|
// 去重
|
|
|
idx = unique(sum, sum + idx) - sum;
|
|
|
|
|
|
// 后半部分搜索 k~n
|
|
|
dfs2(k, 0);
|
|
|
|
|
|
// 输出答案
|
|
|
printf("%d\n", ans);
|
|
|
|
|
|
return 0;
|
|
|
} |
