迭代加深搜索+双向搜索

从初态和终态出发各搜索一半状态&＃xff0c;产生两颗深度减半的搜索树&＃xff0c;在中间教会&＃xff0c;组合成为最终的答案。
双向搜索又名折半搜索。当搜索的复杂度在指数级的时候&＃xff0c;我们可以通过将指数折半的方法降低搜索复杂度。
具体做法是从初态和终态出发各搜索一半状态&＃xff0c;产生两颗深度减半的搜索树&＃xff0c;两颗树交汇在一起形成最终答案&＃xff0c;将O(nk)O(nk)降低到O(nk/2&＃43;nk/2&＃43;1)O(nk/2&＃43;nk/2&＃43;1)的复杂度。
其实对于这样的指数级复杂度&＃xff0c;如果指数除以2后可以接受的话&＃xff0c;可以考虑双向搜索。

CH2401 送礼物

传送门
达达帮翰翰给女生送礼物&＃xff0c;翰翰一共准备了N个礼物&＃xff0c;其中第i个礼物的重量是G[i]。
达达的力气很大&＃xff0c;他一次可以搬动重量之和不超过W的任意多个物品。
达达希望一次搬掉尽量重的一些物品&＃xff0c;请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。

输入格式
第一行两个整数&＃xff0c;分别代表W和N。

以后N行&＃xff0c;每行一个正整数表示G[i]。

输出格式
仅一个整数&＃xff0c;表示达达在他的力气范围内一次性能搬动的最大重量。

数据范围
1≤N≤45,
1≤W,G[i]≤231−1
输入样例&＃xff1a;
20 5
7
5
4
18
1
输出样例&＃xff1a;
19

因为w过大&＃xff0c;没法使用背包&＃xff0c;可是直接的搜索是 O(2N)O(2^N) O(2N)级别的&＃xff0c;可是我们这题的N的范围到45&＃xff0c;正常无法解决。所以考虑双向搜索。
把礼物分为两半&＃xff0c;首从前一半礼物中选出若干个&＃xff0c;可能达到的0~W之间的所有重量值&＃xff0c;放在数组里排序去重。再进行第二次搜索。
对于每一个第一部分达到的重量t&＃xff0c;在第二部分数组中二分查找<&＃61;w-t的数值中的最大值。这个算法的时间复杂度是O(2N/2log2N/2)&＃61;O(N∗2N/2)O(2^{N/2}log2^{N/2})&＃61;O(N*2^{N/2})O(2N/2log2N/2)&＃61;O(N∗2N/2)
分半也存在一些细节可以优化时间&＃xff0c;不要耿直的 N/2&＃xff0c;资料上说 1~N/2&＃43;2 分法经过随机数据验证是最快的。

#include
using namespace std;
const int N&＃61;(1<<24)&＃43;1;
long long ans,n,m,a[N],s[N],n_2;
long long find(int val)//二分查找
{int l&＃61;1,r&＃61;n_2,check&＃61;m-val;//最大可以承受的值while(l<r){int mid&＃61;(l&＃43;r&＃43;1)>>1;if (s[mid]<&＃61;check)l&＃61;mid;elser&＃61;mid-1;}ans&＃61;max(ans,s[l]&＃43;val);//当前最大值与全局最大值开始比较
}
int cmp(long long a,long long b)
{return a>b;
}
int dfs(int x,long long sum)
{if (x&＃61;&＃61;(n/2&＃43;2)&＃43;1){s[&＃43;&＃43;n_2]&＃61;sum;//新的权值出现,压入数组中return true;//返回必不可少,否则RE}dfs(x&＃43;1,sum);//不放这个进去if (sum&＃43;a[x]<&＃61;m)//可以放进去dfs(x&＃43;1,sum&＃43;a[x]);
}
int dfs2(int x,int sum)
{
// cout<if (x&＃61;&＃61;n&＃43;1){find(sum);//求出当前可以填充的最大值return true;} dfs2(x&＃43;1,sum);if (sum&＃43;a[x]<&＃61;m)//如果可以放进去dfs2(x&＃43;1,sum&＃43;a[x]);
}
int main()
{ios::sync_with_stdio(false);cin>>m>>n;for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;)cin>>a[i];sort(a&＃43;1,a&＃43;1&＃43;n,cmp);//从大到小排序dfs(1,0);sort(s&＃43;1,s&＃43;n_2&＃43;1);n_2&＃61;unique(s&＃43;1,s&＃43;n_2&＃43;1)-(s&＃43;1);//去掉重复后,多少个数dfs2(n/2&＃43;3,0);cout<<ans<<endl;return 0;
}