AcWing 171. 送礼物
原题链接
简单
作者:
Anoxia_3
,
2021-05-16 13:05:03
,
所有人可见
,
阅读 330
/*
双向dfs:
用空间换时间,将物品分成两堆,分别求出每堆物品可以凑成的集合s。
然后在从一个集合出发,在另一个集合中找出合法的值。
做法:
1.将所有物品按重量降序排序
2.先将前k键物品能凑出的所有重量打表,然后排序判重
3.搜索剩下的N-K件物品的选择方式,然后在表中二分出不超过W的最大值
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 46;
int n , m , k;
int weight[1 << 25];
int w[N];
int cnt = 1;//记录前半部分元素个数
int ans;
bool cmp(int a , int b)
{
return a > b;
}
void dfs1(int u , int s)//处理前半部分
{
if(u == k)//当遍历完前半部分,打表
{
weight[cnt++] = s;
return;
}
dfs1(u + 1 , s);//不选物品w[u]
if((long long) w[u] + s <= m) dfs1(u + 1 , w[u] + s);//在不超的情况下选物品w[u]
}
void dfs2(int u , int s)//处理后半部分
{
if(u == n)//如果达到深的节点,开始对前半部分进行二分,找最优解
{
int l = 0 , r = cnt - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(weight[mid] <= m - s) l = mid;//找出不超过m-s的最大值
else r = mid - 1;
}
ans = max(ans , weight[l] + s);
return;
}
//这里跟dfs1一样,同样要分叉,但是不用打表
dfs2(u + 1 , s);
if((long long)w[u] + s <= m) dfs2(u + 1 , w[u] + s);
}
int main()
{
cin >> m >> n;
for(int i = 0 ; i < n ; i++) cin >> w[i];
sort(w , w + n , cmp);
k = n / 2 + 2;
dfs1(0 , 0);//预处理前部分
//对前半部分排序、去重,便于二分
sort(weight , weight + cnt);
cnt = unique(weight, weight + cnt) - weight;
dfs2(k , 0);
cout << ans << endl;
return 0;
}