AcWing 171. (upper_bound)
原题链接
简单
作者:
EastofEden
,
2024-07-27 15:28:35
,
所有人可见
,
阅读 1
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int Se = 1 << 25;
//每个物品都有选和不选两种状态,分成一半就是23个
const int N = 50;
typedef long long LL;
int g[N];//每个物品的总重量
int sselect[Se];//每种选择的
int k, cnt = 0, ans = 0,w,tn;
void dfs1(int n,int sum)//sum表示总和,n表示当前枚举到哪一个数了
{
if (n == k)
{
sselect[cnt++] = sum;
return;
}
dfs1(n + 1, sum);//不选当前的物品
if ((LL)sum + g[n] <= w)
{
dfs1(n + 1, sum + g[n]);
}
}
void dfs2(int n,int sum)
{
if (n == tn)
{
int pos = upper_bound(sselect, sselect + cnt, w - sum) - sselect-1;
ans = max(ans, sselect[pos] + sum);
return;
}
dfs2(n + 1, sum);
if ((LL)sum + g[n] <= w)
{
dfs2(n + 1, sum + g[n]);
}
}
int main()
{
cin >> w >> tn;
for (int i = 0; i < tn; i++)
{
cin >> g[i];
}
//优化搜索顺序
sort(g, g + tn);
reverse(g, g + tn);
k = tn >>1;
dfs1(0, 0);
sort(sselect, sselect + cnt);
int t = 1;
for (int i = 1; i < cnt; i++)
if (sselect[i] != sselect[i - 1])
sselect[t++] = sselect[i];
cnt = t;
dfs2(k, 0);
cout << ans << endl;
return 0;
}