算法提高课汇总

双向$dfs$

基本原理与双向$bfs$ 相同:

算法思路

本题可看成重量和价值均为$G(i)$的背包问题, 时间复杂度$O(NV)$, 超时.

由于$N$比较小, 可以考虑枚举所有选法, 时间复杂度$O(2^N) = 2^{46}$, 仍无法接受.

双向$dfs$优化

可以先搜索前$N/2$个物品所有选法对应的重量集合, 并存储在$weights[]$中.

在枚举后$N/2$个物品所有选择方案每次得到重量$s$, 对于每个$s$, 查询$s + weight[i]\le w$
的最大值. 可以用二分实现.

这里蕴含的思想是用空间换时间: 在搜索后$N/2$物品的重量$s$后, 由于前$N/2$所有方案对应体积
已经存储, 所以不需要再次暴搜, 而使用二分快速查表.

调整双向折半点

考虑上述思路时间复杂度: $O(2^{N/2} + 2^{N/2}\times \lg(2^{N/2})) = (N/2 + 1)\times 2^{N/2}\approx 1.9\times 10^8$

接近$10^8$ — “性感的数字”. 由于后半部分的搜索还包括二分, 可以适当让前半部分多搜索点.

假设前半部分搜索$K$个数字, 时间复杂度: $O(2^K + 2^{N-K}\times \lg(2^K)) = 2^K + K\times 2^{N - K}$.

可以取$K = N / 2 + 2$, $N = 46$时, $K = 25$, $T = 2^{25} + 25\times 2^{21} = (16 + 25)\times 2^{21}\approx 8\times 10^7$

剪枝优化

• 优化搜索顺序: 枚举物品时, 按重量从大到小的顺序枚举 — 重量更大, 更快到达上限$W$,
  对应搜索树层数更小.

• 可行性剪枝: 选择某物品时, 要满足之前选择物品的总重量加上当前物品重量不超过重量上限$W$.

具体代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 46, K = N / 2 + 2;

int n, m, k;
int w[N];
int weights[1 << K], cnt;
int ans;

void dfs1(int u, int s)
{
    if ( u == k )
    {
        weights[cnt ++] = s;
        return;
    }

    dfs1(u + 1, s);
    if ( (ll)s + w[u] <= m )    dfs1(u + 1, s + w[u]); //可行性
}

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

    dfs2(u + 1, s);
    if ( (ll)s + w[u] <= m )    dfs2(u + 1, s +w[u]); //可行性
}

int main()
{
    cin >> m >> n;
    for ( int i = 0; i < n; i ++ )  cin >> w[i];

    //优化搜索顺序
    sort(w, w + n);
    reverse(w, w + n);

    //前半部分: 0 ~ k - 1
    k = n / 2 + 2;
    dfs1(0, 0);

    sort(weights, weights + cnt);
    cnt = unique(weights, weights + cnt) - weights;

    //后半部分: k ~ n - 1
    dfs2(k, 0);
    cout << ans << endl;
}