1、B站視頻鏈接：B26 雙向DFS 送禮物_嗶哩嗶哩_bilibili
#include <bits/stdc++.h>
using namespace std;
int n,m;
int g[46];//存儲所有物品的質量
int w[1<<23];//存儲所有能湊出來的重量
int ans,cnt;//w的個數是cnt//搜索第u個數，和為s;
void dfs1(int u,int s){if(u==n/2){//邊界 w[cnt++]=s;return;}dfs1(u+1,s);//不選g[u]if(g[u]+s<=m)dfs1(u+1,s+g[u]);//選
}
void dfs2(int u,int s){if(u==n){ans=max(ans,*(upper_bound(w,w+cnt,m-s)-1)+s);return;}dfs2(u+1,s);//不選g[u] if(g[u]+s<=m)dfs2(u+1,s=g[u]);//選
}
int main(){cin>>m>>n;for(int i=0;i<n;i++)cin>>g[i];sort(g,g+n);reverse(g,g+n);//優化搜索順序dfs1(0,0);//搜索前一半n/2sort(w,w+cnt);cnt=unique(w,w+cnt)-w;//去重dfs2(n/2,0);//搜索后一半(n/2,n); cout<<ans;return 0;
} ?
)
