#define maxn 0x3f3f3f3f
时间: 2023-10-25 17:07:20 浏览: 49
这是一个宏定义,将`maxn`定义为一个十六进制数`0x3f3f3f3f`。在计算机科学中,经常会用到一些特殊的数字作为标记,例如用全1二进制数表示“最大值”或“无穷大”,用全0二进制数表示“最小值”或“无穷小”。`0x3f3f3f3f`即为这样的一个标记,表示int类型的最大值。在一些算法中,这个标记经常被用来表示“无穷大”或“不可达”。
相关问题
#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #include<queue> #include<stack> #include<math.h> #include<map> typedef long long int ll; using namespace std; #define maxn 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f const int mm=1e6+100; ll d[mm]; struct f{ ll a,b; }num[mm]; bool cmp(f k,f kk) { if(k.a!=kk.a) return k.a<kk.a;//a升序 else return k.b>kk.b;//b降序 } int main() { ll n,m,i,j,t,a,b,c,p,k,kk,l,r; scanf("%lld%lld",&n,&m); for(i=1;i<=n;i++) scanf("%lld",&d[i]); for(i=1;i<=m;i++) scanf("%lld",&num[i].a); for(i=1;i<=m;i++) scanf("%lld",&num[i].b); sort(num+1,num+1+m,cmp); for(i=1;i<=m;i++) { num[i].b=max(num[i-1].b,num[i].b); } ll sum=0; for(i=1;i<=n;i++) { l=0; r=m; p=0; while(l<=r) { ll mid=(l+r)/2; if(d[i]>num[mid].a) { p=mid; l=mid+1; } else r=mid-1; } sum+=num[p].b; } printf("%lld\n",sum); }解释这段代码
这段代码实现了一个题目的解法。具体题目不清楚,但代码中的变量名和注释可以大致理解其思路。
首先,读入一个数列 `d` 和一些二元组 `(a,b)`,并将这些二元组按照 `a` 为第一关键字升序排序,`b` 为第二关键字降序排序。然后,对于每个 `d[i]`,在排序后的二元组中二分查找第一个 `a` 大于等于 `d[i]` 的二元组,并累加其对应的 `b` 值。
具体来说,变量解释如下:
- `n`:数列 `d` 的长度。
- `m`:二元组的数量。
- `num`:存储二元组的数组。
- `d`:存储数列的数组。
- `cmp`:比较函数,按照上述方式比较两个二元组大小。
- `l`、`r`、`mid`、`p`:二分查找时使用的变量。
- `sum`:累加的结果,即所有 `d[i]` 对应的 `b` 值之和。
具体实现细节见代码注释:
//采用队列式分枝限界法求解0/1背包问题的算法 #include <stdio.h> #include <queue> #include <iostream> using namespace std; #define MAXN 20 //最多可能物品数 #define INF 0x3f3f3f3f3 //定义∞ //问题表示 int n,W; int w[MAXN+1]; //重量,下标0不用 int v[MAXN+1]; //价值,下标0不用 //求解结果表示 int maxv=-9999; //存放最大价值,全局变量 int bestx[MAXN+1]; //存放最优解,全局变量 int total=1; //解空间中结点数累计,全局变量 struct NodeType //队列中的结点类型 { int no; //结点编号 int i; //当前结点在搜索空间中的层次 int w; //当前结点的总重量 int v; //当前结点的总价值 int x[MAXN]; //当前结点包含的解向量 double ub; //上界 bool operator<(const NodeType &s) const //重载<关系函数 { return ub<s.ub; //ub越大越优先出队 } }; void bound(NodeType &e); //计算分枝结点e的上界 void EnQueue(NodeType e,priority_queue<NodeType> &qu); //结点e进队qu void bfs(); //求0/1背包的最优解 int main() { cin>>n>>W; //输入物体个数及背包载重量 for(int i=1;i<=n;i++)//输入各物体重量及价值 cin>>w[i]>>v[i]; bfs(); //调用队列式分枝限界法求0/1背包问题 for(int i=1;i<=n;i++) printf("%d",bestx[i]); //输出所求X[n]数组 printf("\n%d",maxv); return 0; } /* 请在这里填写答案 */
答案:
```cpp
//采用队列式分枝限界法求解0/1背包问题的算法
#include <stdio.h>
#include <queue>
#include <iostream>
using namespace std;
#define MAXN 20 //最多可能物品数
#define INF 0x3f3f3f3f3 //定义∞
//问题表示
int n,W;
int w[MAXN+1]; //重量,下标0不用
int v[MAXN+1]; //价值,下标0不用
//求解结果表示
int maxv=-9999; //存放最大价值,全局变量
int bestx[MAXN+1]; //存放最优解,全局变量
int total=1; //解空间中结点数累计,全局变量
struct NodeType //队列中的结点类型
{
int no; //结点编号
int i; //当前结点在搜索空间中的层次
int w; //当前结点的总重量
int v; //当前结点的总价值
int x[MAXN]; //当前结点包含的解向量
double ub; //上界
bool operator<(const NodeType &s) const //重载<关系函数
{
return ub<s.ub; //ub越大越优先出队
}
};
void bound(NodeType &e); //计算分枝结点e的上界
void EnQueue(NodeType e,priority_queue<NodeType> &qu); //结点e进队qu
void bfs(); //求0/1背包的最优解
int main() {
cin>>n>>W; //输入物体个数及背包载重量
for(int i=1;i<=n;i++)//输入各物体重量及价值
cin>>w[i]>>v[i];
bfs(); //调用队列式分枝限界法求0/1背包问题
for(int i=1;i<=n;i++)
printf("%d",bestx[i]); //输出所求X[n]数组
printf("\n%d",maxv);
return 0;
}
void bound(NodeType &e){
int i=e.i+1;
int wt=e.w;
double bound=e.v;
while(i<=n && wt+w[i]<=W){
wt+=w[i];
bound+=v[i];
i++;
}
if(i<=n){
bound+=(W-wt)*(v[i]*1.0/w[i]);
}
e.ub=bound;
}
void EnQueue(NodeType e, priority_queue<NodeType> &qu){
if(e.i==n){
if(e.v>maxv){
maxv=e.v;
for(int j=1;j<=n;j++){
bestx[j]=e.x[j];
}
}
return;
}
NodeType e1=e,e2=e;
e1.x[e.i+1]=0;
bound(e1);
if(e1.ub>maxv){
e1.i=e.i+1;
EnQueue(e1,qu);
}
e2.x[e.i+1]=1;
bound(e2);
if(e2.ub>maxv){
e2.i=e.i+1;
e2.v=e.v+v[e.i+1];
e2.w=e.w+w[e.i+1];
EnQueue(e2,qu);
}
}
void bfs(){
priority_queue<NodeType> qu;
NodeType e;
e.i=0;
e.w=0;
e.v=0;
bound(e);
qu.push(e);
while(!qu.empty()){
e=qu.top();
qu.pop();
total++;
EnQueue(e,qu);
}
}
```