int bestx[MAXN];为什么报错
时间: 2023-06-20 13:05:56 浏览: 100
在 C++ 中,如果你在函数外部声明一个数组,那么这个数组的大小必须是一个常量表达式。也就是说,你不能使用变量来定义数组的大小。例如,下面的代码是合法的:
```
const int MAXN = 100;
int bestx[MAXN];
```
而下面的代码是非法的:
```
int n = 100;
int bestx[n]; // error: variable-sized object may not be initialized
```
如果你需要在函数内部定义一个动态大小的数组,你可以使用动态内存分配来实现。例如,下面的代码使用 `new` 运算符在堆上分配了一个数组:
```
int n = 100;
int* bestx = new int[n]; // allocate an array of size n on the heap
// ...
delete[] bestx; // free the memory when you're done using it
```
需要注意的是,使用动态内存分配来创建数组会增加代码的复杂度,需要在使用完数组后手动释放内存,否则会造成内存泄漏。
相关问题
//采用队列式分枝限界法求解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);
}
}
```
#include<stdio.h> #define MAXN 102 #define MAXM 102 //问题表示 int n; //部件数 int m; //供应商数 int cost; //限定价格 int w[MAXN][MAXM]; //w[i][j]为第i个零件在第j个供应商的重量 int c[MAXN][MAXM]; //c[i][j]为第i个零件在第j个供应商的价格 //求解结果表示 int bestx[MAXN]; int x[MAXN]; int cw=0,cc=0; int bestw=999999; bool find(int i,int j) //如果j在x[1..i-1]中出现,返回true,否则返回false { for (int k=1;k<i;k++) if (x[k]==j) return true; return false; } void dfs(int i) //求解算法 { /*补齐代码*/ } int main() { int i,j; scanf("%d%d%d",&n,&m,&cost); //输入部件数,供应商数,限定价格 for(i=1; i<=n; i++) //输入各部件的在不同供应商的重量 for(j=1; j<=m; j++) scanf("%d",&w[i][j]); for(i=1; i<=n; i++) //输入各部件的在不同供应商的价格 for(j=1; j<=m; j++) scanf("%d",&c[i][j]); dfs(1); //i从1开始搜索 for(i=1;i<=n;i++) //输出每个部件的供应商 printf("%d ",bestx[i]); printf("\n%d\n",bestw); //输出最小重量 return 0; }补全代码
以下是补全代码部分:
void dfs(int i) {
if(i>n) {
if(cw<=cost && cc<bestw) {
bestw=cc;
for(int j=1;j<=n;j++) bestx[j]=x[j];
}
return;
}
for(int j=1;j<=m;j++) {
if(find(i,j)) continue;
x[i]=j;
cw+=w[i][j];
cc+=c[i][j];
dfs(i+1);
cw-=w[i][j];
cc-=c[i][j];
}
}
首先判断是否搜索完所有部件,如果是,判断当前是否符合要求,并更新最小重量和最优解。如果未搜索完所有部件,就从所有供应商中选择一个,如果该供应商已经选过了就跳过,否则更新当前状态并进入下一层搜索。搜索完后,记得回溯状态。
阅读全文