送礼物

达达帮翰翰给女生送礼物，翰翰一共准备了 $N$ 个礼物，其中第 $i$ 个礼物的重量是 $G[i]$。

达达的力气很大，他一次可以搬动重量之和不超过 $W$ 的任意多个物品。

达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。

输入格式

第一行两个整数，分别代表 $W$ 和 $N$。

以后 $N$ 行，每行一个正整数表示 $G[i]$。

输出格式

仅一个整数，表示达达在他的力气范围内一次性能搬动的最大重量。

数据范围

$1\le N\le 46$,
$1\le W,G[i]\le 2^{31}-1$

输入样例：

20 5
7
5
4
18
1

输出样例：

19

思路

就是从中选择一些数相加, 他们的和需要小于$W$, 求能构成的最大数。如果用动态规划背包做的话, 时间复杂度为$O(NV)$ , 这里体积为 $2^{31}-1$, 肯定超时。

考虑爆搜, 搜索顺序： u为当前枚举的位置, s为当前得到的和

剪枝优化：

1. 先搜分支小的, 故为逆向搜索
2. 采用双向DFS搜索, 节省时间

双向DFS搜索是指从起点和终点同时搜索, 交汇时就是最终结果, 相比从起点搜到非常深的位置, 这样会少搜一些。用空间换时间。

该题的话就设定一个weight存前半个数组的所有相加和结果, 先DFS前一半数, 每个数选和不选两种情况, 先搜不选的情况, 然后判断是否会超过w（剪枝）再搜选的情况。 其时间复杂度为$O(2^{n-k}+2^k\times {\log }_2{2}^k)$ 即$O(2^{n-k}+2^k\times k)$ , n-k为前半部分搜索的复杂度, k为二分搜索 $s+weigh{t}_i\le w$ 中最大的 $weigh{t}_i$, 也就是最大的$weigh{t}_i\le w-s$ 。 这里则设定 $n-k=\frac{n}{2}$ , 复杂度为$O(2^{23}+2^{23}\times 23)$ 。 若按之前设定为 $n-k=\frac{n}{2}+2$, 复杂度为 $O(2^{25}+2^{21}\times 25)$

DEBUG 段错误时可以用 exit(0) 来在某行退出, 若可以则在其之上的代码都没问题

代码

const int N = 47;
typedef long long LL;
int a[N];
int n, w, k;
int weight[1 << 25], cnt = 1;
int ans;
void dfs1(int u, int s)
{
    if (u == k)
    {
        weight[cnt++] = s;
        return;
    }
 
    dfs1(u + 1, s);
    if (a[u] <= w - s)
        dfs1(u + 1, s + a[u]);
}
 
void dfs2(int u, int s)
{
    if (u >= n)
    {
        int l = 0, r = cnt - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (weight[mid] <= w - s)
                l = mid;
            else
                r = mid - 1;
        }
        // cout << s << " " << weight[l] << endl;
        ans = max(ans, weight[l] + s);
        return;
    }
 
    dfs2(u + 1, s);
    if (a[u] <= w - s)
        dfs2(u + 1, a[u] + s);
}
 
int main()
{
    cin >> w >> n;
 
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n, greater<int>());
    k = n / 2;
    dfs1(0, 0);
 
    sort(weight, weight + cnt);
    cnt = unique(weight, weight + cnt) - weight;
 
    dfs2(k, 0);
 
    cout << ans << endl;
    return 0;
}