这题让我不看答案我一辈子写不出来
这道题正常情况下用暴力搜索或者背包问题都能做,但是会超时
于是做优化使$O(2^{45})$转化为$2*O(2^{23})$就刚好能过
优化流程为
- 先列举前$N/2$个物品所能出现的所有情况,这里是$O(2^{23})$
- 再列举后$N/2$个物品出现的所有情况,也是$O(2^{23})$
- 前后组合,对每一个2情况,寻找最适合的1情况,这里寻找用的是二分,复杂度为$2^K*KlogK$,其中$K = N/2$
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 48;
int a[N];
int w,n,k;
long long part[1<<25];
long long ans ,cnt;
void dfs_1(int u,long long s)
{
if(u==k)
{
part[cnt++] = s;
return ;
}
if(s+a[u] <=w) dfs_1(u+1,s+a[u]);
dfs_1(u+1,s);
}
void dfs_2(int u,long long s)
{
if(u == n)
{
int l = 0,r= cnt-1;
while(l<r)
{
int mid = l+r+1>>1;
if(part[mid]+s<=w) l =mid;
else r = mid-1;
}
if(part[r]+s<=w) ans = max(ans, part[r]+s);
return ;
}
if(s+a[u]<=w) dfs_2(u+1, s+a[u]);
dfs_2(u+1,s);
}
int main()
{
cin>>w>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
reverse(a,a+n);
k = (n/2)+2;
dfs_1(0,0);
sort(part,part+cnt);
cnt = unique(part,part+cnt)-part;
dfs_2(k,0);
cout<<ans<<endl;
return 0;
}