【Acwing171】送礼物（双向dfs）题解

本题思路来源于acwing算法提高课

题目描述

 看本文需要准备的知识

1.二分（强烈推荐文章：一分钟学会二分模板 

2.dfs基本思想，了解“剪枝”这个术语

思路分析

首先这道题目看起来就是一个01背包，但是如果直接用01背包去做，时间复杂度为2^31*46一定会超时，如果直接使用爆搜，也一定会超时+爆栈，此时，我们对爆搜进行优化，采用双向dfs去搞定这个题目

整体思路是下面的两步

step one：使用爆搜对前N/2个礼物打表（下面会说这里的打表具体指什么），需要的时间复杂度是2^(N/2)

step two：对剩下的N/2个礼物进行爆搜，对搜索树最后一层的每个结点的“礼物重量和”s使用二分，从前N/2个礼物的打表中找到最大不超过w-s的值（w是能拿的礼物重量的上限），求所有这些值的最大值ans

第一个问题，step one中的打表是什么，比如有三个礼物，重量分别为1,2,3，可以打表的个数为2^3个，分别是0,1,2,3,3,4,5,6，其实就是所有礼物的重量组合，很明显，打表之后会出现重量重复的情况，所以可以通过去重做一个小优化，此处去重是使用头文件<algorithm>中的unique函数，假设打表后的数组为weight,元素总个数为cnt，则可以写（排序之后再用）：

cnt=unique(weight,weight+cnt)-weight;

第二个问题，step two中“搜索树最后一层的每个结点的礼物重量和”是什么意思，其实这个跟对前N/2个礼物打表是完全等价的，只不过是对后N/2个礼物进行打表并且这个结果没有记录下来而是当场直接使用了而已，具体的意思可以看代码理解

最后，还可以做一个小优化就是把刚开始的重量数组g[46]从大到小排序，这实际上是优化搜索顺序，减少递归树的分支

完整代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=50;
typedef long long LL;
int g[N];
int weight[1<<25],cnt;
int n,w,k;
int ans=0;
void dfs1(int u,int s)
{if(u==k){//cout<<u<<" "<<s<<endl;weight[cnt++]=s;return;}dfs1(u+1,s);if((LL)s+g[u]<=w)dfs1(u+1,s+g[u]);
}
void dfs2(int u,int s)
{if(u==n){int l=-1,r=cnt;while(l+1!=r){int mid=(l+r)/2;if(weight[mid]<=w-s)l=mid;else r=mid;}//cout<<weight[l]+s<<endl;if (weight[l]+(LL)s<=w)ans=max(ans,weight[l]+s);return;}dfs2(u+1,s);if((LL)s+g[u]<=w)dfs2(u+1,s+g[u]);
}
int main()
{cin>>w>>n;for(int i=0;i<n;i++)cin>>g[i];sort(g,g+n);reverse(g,g+n);k=n/2; dfs1(0,0);sort(weight,weight+cnt);// for(int i=0;i<cnt;i++)cout<<weight[i]<<endl;cnt=unique(weight,weight+cnt)-weight;//  for(int i=0;i<cnt;i++)cout<<weight[i]<<endl;dfs2(k,0);cout<<ans<<endl;return 0;
}