折半枚举(双向搜索)
搜索 双向 枚举 折半
2023-06-13 09:14:16 时间
折半枚举的思想来源于双向搜索,主要解决的就是当问题规模较大时,无法枚举所有元素的组合,但能枚举一半元素的组合.
题目:POJ2785
题目大概意思就是给出ABCD四个数列,每个数列有n个整数.从四个数列各取出一个数,将他们相加.求和为0的组合个数.
如果直接暴力求解的话,时间复杂度是O(N4),是不可接受的.
但是如果折半来枚举,只要分别枚举每个A+B,和C+D,求能够使得(A+B)=-(C+D)的组合数就行了.这样子时间复杂度就降低到了O(N2).
AC代码
#pragma GCC optimize("Ofast")
#include<algorithm>
#include<cstdio>
using namespace std;
#define MAXN 4005
typedef long long ll;
ll a[MAXN], b[MAXN], c[MAXN], d[MAXN];
ll CD[MAXN*MAXN];
int n;
int main()
{
scanf("%d", &n);
for(int i=0;i<n;++i)
{
scanf("%lld%lld%lld%lld", &a[i], &b[i], &c[i], &d[i]);
}
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
CD[i*n+j] = c[i]+d[j];
}
ll n2 = n*n;
sort(CD, CD+n2);
ll tmp;
ll ans=0;
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
tmp = -(a[i]+b[j]);
ans += upper_bound(CD, CD+n2, tmp) - lower_bound(CD, CD+n2, tmp);
}
}
printf("%lld\n", ans);
}
超大背包问题
当背包问题的规模很大时,算法的时间复杂度是指数级增长的,那么将无法解决问题.
折半枚举就可以分别枚举数组的前半部分和后半部分.
首先,对w和v建立一个pair,然后按照字典序进行排序.接着,枚举前半部分,然后去除多余的组合(其实就是去除性价比很低的物品,也就是重量大,价值还低的)
然后枚举后半部分,并且在前半部分中搜索满足”前半重量比(最大重量-后半部分重量)小”的组合,然后求两部分价值相加的最大值.
相关文章
- PyCharm使用教程 — 9、PyCharm中的搜索技巧(文件/函数/内容)「建议收藏」
- 剑指offer No.26 二叉搜索树与双向链表
- 【题解】动态规划法实现穷举搜索(ALDS1_5_A)
- 找资源什么的,这样搜索才高效
- 把你的人生数据化,然后随时翻看,你愿意吗?这款搜索app就这么干了
- Typecho 无插件实现即时搜索
- PHP preg_filter():执行一个正则表达式的搜索和替换
- 搜索神器——Linux命令行(linux命令行搜索)
- 二叉搜索树与双向链表算法详解编程语言
- 百度搜索指数是什么意思?
- 探索Linux:字符搜索功能(linux字符搜索)
- Microsoft 365用户或很快能够获取使用微软搜索等服务的积分
- 搜索Linux访问谷歌:从入门到精通(linux访问谷歌)
- 极速搜索:Linux下的种子搜索神器(linux种子搜索器)
- 搜索用Oracle数据库实现模糊搜索:简易实现步骤(oracle查询模糊)
- 什么SQL Server分页技术:利用它实现数据精准搜索(sqlserver分页是)
- Redis自动补全实现实时数据搜索(自动补全 redis)
- 推荐js实现商品分类到搜索栏友好提示(人机交互)