題目鏈接：點(diǎn)擊查看

題目大意：給出n個(gè)禮物，以及最大承重量，問在最大承重量?jī)?nèi)所搬的禮物最重是多少

題目分析：因?yàn)槊總€(gè)禮物只有搬或不搬兩種狀態(tài)，所以我們可以直接搜索，但是題目給出的N最大到了46，直接搜的話時(shí)間復(fù)雜度到了2的46次方，肯定會(huì)T，那么我們?cè)撛趺磧?yōu)化呢，這里用到了雙向搜索的技巧，先上定義：（摘自zx學(xué)長(zhǎng)的ppt）

雙向搜索：

除了迭代加深以外，雙向搜索也可以避免在深層子樹上浪費(fèi)時(shí)間。在一些題目中，問題不但具有初態(tài)，還具有明確的終態(tài)，并且從初態(tài)開始搜索與從終態(tài)開始逆向搜索產(chǎn)生的搜索樹都能覆蓋整個(gè)狀態(tài)空間。在這種情況下，就可以采取雙向搜索——從初態(tài)和終態(tài)出發(fā)各搜索一半狀態(tài)，產(chǎn)生兩棵深度減半的搜索樹，在中間交匯，組合成最終的答案。

?既然提到雙向，我們就可以直接將n除以二來對(duì)待，這樣一來時(shí)間復(fù)雜度瞬間下降到了2的23次方，差不多1e7不到，題目給了3秒可以應(yīng)付，下面講一下大體思路

首先我們可以將禮物折半分成兩部分，用搜索先將第一部分的禮物可以組合的所有情況都搜出來，記錄下來并去重，然后開始搜另一部分的禮物，每次搜到盡頭時(shí)，用二分查找一下在不超過最大承重的范圍內(nèi)，所能和當(dāng)前結(jié)果組成的最大結(jié)果是多少，并實(shí)時(shí)更新答案，總的時(shí)間復(fù)雜度為，就可以完美解決這個(gè)問題了

再來說一下幾個(gè)可以優(yōu)化剪枝的點(diǎn)吧：

一開始可以對(duì)禮物進(jìn)行降序排序，排序后再折半搜索

因?yàn)榈谝淮嗡阉鞯臅r(shí)間復(fù)雜度是，而第二次搜索多了個(gè)二分的時(shí)間開銷，變?yōu)榱?#xff0c;所以我們可以適當(dāng)增加第一次搜索的深度，從而減少第二次搜索的深度，經(jīng)過多次提交測(cè)試出來第一次取值為(n/2)+2最為合適，比(n/2)的速度快了一倍

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=50;LL n,w,ans;int cnt,limit;LL a[N],temp[(1<<25)+10];void dfs1(int pos,LL sum) {if(pos==limit){temp[cnt++]=sum;return;}if(sum+a[pos]<=w)dfs1(pos+1,sum+a[pos]);dfs1(pos+1,sum); }void dfs2(int pos,LL sum) {if(pos==n){int t=lower_bound(temp,temp+cnt,-(w-sum))-temp;ans=max(ans,sum-temp[t]);return;}if(sum+a[pos]<=w)dfs2(pos+1,sum+a[pos]);dfs2(pos+1,sum); }bool cmp(const LL& a,const LL& b) {return a>b; }int main() { // freopen("input.txt","r",stdin);while(scanf("%lld%lld",&w,&n)!=EOF){for(int i=0;i<n;i++)scanf("%lld",a+i);sort(a,a+n,cmp);limit=n/2+2;//選擇適當(dāng)?shù)恼郯朦c(diǎn)，算是一種剪枝cnt=0;dfs1(0,0);cnt=unique(temp,temp+cnt)-temp;for(int i=0;i<cnt;i++)temp[i]=-temp[i];sort(temp,temp+cnt);temp[cnt]=0;ans=0;dfs2(limit,0);printf("%lld\n",ans);}return 0; }

?

超強(qiáng)干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的AcWing - 171 送礼物(双向dfs)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。