#include
#include
#include
#include
using namespace std;
ifstream infile;
ofstream outfile;
class Node
{
friend int func(int*, int, int, int*);
public:
int ID;
double weight;//物品的重量
};
bool comp1(Node a, Node b) //定义比较规则
{
return a.weight > b.weight;
}
class Load;
class bbnode;
class Current
{
friend Load;
friend struct Comp2;
private:
int upweight;//重量上界
int weight;//结点相应的重量
int level;//活结点在子集树中所处的层次
bbnode* ptr;//指向活结点在子集树中相应结点的指针
};
struct Comp2
{
bool operator () (Current *x, Current *y)
{
return x->upweightupweight;
}
};
class Load
{
friend int func(int*, int, int, int*);
public:
int Max0();
private:
priority_queue, Comp2>H;//利用优先队列（最大堆）储存
int limit(int i);
void AddLiveNode(int up, int cw, bool ch, int level);
bbnode *P;//指向扩展结点的指针
int c;//背包的容量
int n;//物品的数目
int *w;//重量数组
int cw;//当前装载量
int *bestx;//最优解方案数组
};
class bbnode
{
friend Load;
friend int func( int*, int, int, int*);
bbnode* parent;
bool lchild;
}; //结点中有双亲指针以及左儿子标志
int Load::limit(int i) //计算结点所相应重量的上界
{
int left,a;
left= c - cw;//剩余容量
a = cw; //b是重量上界，初始值为已经得到的重量
while (i <= n && w[i] <= left)
{
left -= w[i];
a += w[i];
i++;
}
return a;
}
void Load::AddLiveNode(int up, int cw, bool ch, int level) //将一个新的活结点插入到子集树和优先队列中
{
bbnode *b = new bbnode;
b->parent = P;
b->lchild = ch;
Current* N = new Current;
N->upweight = up;
N->weight = cw;
N->level = level;
N->ptr = b;
H.push(N);
}
int Load::Max0()
{
int i = 1;
P = 0;
cw = 0;
int bestw = 0;
int up = limit(1);
while (i != n + 1)
{
int wt = cw + w[i]; //检查当前扩展结点的左儿子结点
if (wt <= c)//左儿子结点是可行结点
{
if (wt > bestw)
bestw =wt;
AddLiveNode(up,wt, true, i + 1);
}
up = limit(i + 1); //检查当前扩展结点的右儿子结点
if (up >= bestw)//如果右儿子可行
{
AddLiveNode(up,cw, false, i + 1);
}
Current* N = H.top(); //取队头元素
H.pop();
P = N->ptr;
cw = N->weight;
up = N->upweight;
i = N->level;
}
bestx = new int[n + 1];
for (int j = n; j > 0; --j)
{
bestx[j] = P->lchild;
P = P->parent;
}
return cw;
}
int func(int *w, int c, int n, int *bestx) //调用Max0函数对子集树的优先队列式进行分支限界搜索
{
int W = 0; //初始化装载的总质量为0
Node* Q = new Node[n];
for (int i = 0; i < n; ++i)
{
Q[i].ID = i + 1;
Q[i].weight = w[i+1];
W += w[i+1];
}
if (W <= c)//如果足够装，全部装入
return W;
sort(Q, Q + n, comp1); //首先，将各物品按照重量从大到小进行排序；
Load K;
K.w = new int[n + 1];
for (int j = 0; j < n; j++)
K.w[j + 1] = w[Q[j].ID];
K.cw = 0;
K.c = c;
K.n = n;
int bestp = K.Max0();
for (int k = 0; k < n; k++)
{
bestx[Q[k].ID] = K.bestx[k + 1];
}
delete []Q;
delete []K.w;
delete []K.bestx;
return bestp;
}
int main()
{
int*w,*Final;
int c,n,i,best;
infile.open("input.txt",ios::in);
if(!infile)
{
cerr<<"open error"<>c;
infile>>n;
w=new int[n+1];
for(i=1;i<=n;i++)
infile>>w[i];
infile.close();
Final = new int[n+1];
best = func( w, c, n, Final);
outfile.open("output.txt",ios::out);
if(!outfile)
{
cerr<<"open error"<
2022-06-07 18:10:13
4KB
1
使用分支限界法解决N皇后问题。因为是广度优先，而且占用比较多的额外空间，所以并不是解N皇后问题的很好的算法，主要是理解分支限界法的使用。
2022-05-20 23:16:36
2KB
1