网站方案策划,用php做注册网站的代码,wdcp搭建网站,linux上安装wordpress有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船#xff0c;其中集装箱i的重量为Wi#xff0c;且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有#xff0c;找出一种装载方案。
容易证明#xff1a;如果一个给定装载问题有解#xff…有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船其中集装箱i的重量为Wi且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有找出一种装载方案。
容易证明如果一个给定装载问题有解则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满 (2)将剩余的集装箱装上第二艘轮船。 思想 在算法的循环体中首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后当前扩展结点被舍弃。
活结点队列中的队首元素被取出作为当前扩展结点由于队列中每一层结点之后都有一个尾部标记-1故在取队首元素时活结点队列一定不空。当取出的元素是-1时再判断当前队列是否为空。如果队列非空则将尾部标记-1加入活结点队列算法开始处理下一层的活结点。
节点的左子树表示将此集装箱装上船右子树表示不将此集装箱装上船。设bestw是当前最优解ew是当前扩展结点所相应的重量r是剩余集装箱的重量。则当ewrbestw时可将其右子树剪去因为此时若要船装最多集装箱就应该把此箱装上船。另外为了确保右子树成功剪枝应该在算法每一次进入左子树的时候更新bestw的值。
为了在算法结束后能方便地构造出与最优值相应的最优解算法必须存储相应子集树中从活结点到根结点的路径。为此目的可在每个结点处设置指向其父结点的指针并设置左、右儿子标志。 找到最优值后可以根据parent回溯到根节点找到最优解。优先队列写法
#includeiostream
#includequeue//优先队列的头文件
using namespace std;
//子集树中节点的定义
class bbnode{ public:bbnode *parent;//指向父节点的指针 bool Lchild;//是否是左孩子结点的标记
};
//优先队列中节点的定义
class HeapNode{public:bbnode *ptr; //指向活结点在子集树中相应节点的指针int uweight; //活结点的优先级(上界) //优先级的定义从根节点到节点x的路径相应的载重量加上剩余集装箱的重量之和int level; //活结点在子集树中所处的层次
};
struct compare{bool const operator()(HeapNode *a,HeapNode *b){return (a-uweight) (b-uweight);//最大堆 }
};
//该函数是将新产生的活结点加入到子集树中并将这个节点插入到表示活结点优先队列的最大堆中
void AddLiveNode(priority_queueHeapNode*,vectorHeapNode*,compare Q,bbnode *parent,bool isLeft,int uWeight,int level)
{//先在子集树中建立这个节点bbnode *b new bbnode;b-parent parent;b-Lchild isLeft;//再在优先队列中新建一个节点HeapNode *h new HeapNode;h-ptr b;//将刚在添加到子集树中的新节点b再赋值给将要添加到优先队列中的节点h h-uweight uWeight;h-level level; //将新建的节点添加到优先队列Q.push(h); }int MaxLoading(int *weight,int n,int *bestx,int c)
{priority_queueHeapNode*,vectorHeapNode*,compare Heap;int i0;// 表示当前所在子集树的层次int now_weight0;//表示当前已装载的重量int node_priority0; //优先级————装载的最大上界当前装载量剩余集装箱的重量HeapNode *H;//用于保存从优先队列出来的节点 bbnode *B;//子集树上的扩展节点int *remains; //剩余集装箱 记载未装的货物remains new int[n];remains[n-1]0;//当到达最后的叶子节点时没有剩余的货物 for(int jn-2;j0;j--){ //计算当到达指定层时的剩余数组 remains[j]remains[j1]weight[j1];}while(i!n)//没有到达叶子节点时 ,到达第i层 {if(now_weightweight[i]c)//即当前的重量能够装的下 进入左子树 左孩子 {node_priority(now_weightweight[i]) remains[i];//优先级 当前装载量剩余集装箱的重量AddLiveNode(Heap,B,true,node_priority,i1);}// 进入右子树 右孩子 node_priority(now_weight) remains[i];//优先级 当前装载量剩余集装箱的重量AddLiveNode(Heap,B,false,node_priority,i1);H Heap.top(); //查询优先队列队头结点 Heap.pop(); //队头结点出队 iH-level;BH-ptr; //记录当前到达的结点 now_weightH-uweight - remains[i-1]; //计算当前已经装载量 }// 记录已装载货物 for(int jn-1;j0;j--){bestx[j]B-Lchild? 1:0;BB-parent;}return now_weight; //返回最优装载量 }
int main()
{int n; //货物数 int shipNum; //货船数量 int bestw; //最优装载量 int weight[n]; //货物总重量 int bestx[n]; //最优的装载序列 int c10; //第一艘船的装载重量 int c20; //第二艘船的装载重量 cout请输入货物数;cinn;cout请输入货船的数量;cinshipNum;cout请输入货物的重量序列;for(int i0;in;i){cinweight[i];}cout请输入两艘船的载重量;cinc1c2;int maxc0;//船的最大装载重量 int sumcc1c2;//船的装载重和 if(c1c2)maxcc1;else maxcc2;int maxweight0;//货物中的最大重量int sumweight0; //货船总重量 for(int i0;in;i){if(weight[i]maxweight){maxweightweight[i];}sumweightweight[i];}if(maxweightmaxc){printf(货物重量超过货船的载重量无法装载);return 0;} if(sumweightsumc){printf(货物总重量超过货船的总载重量无法装载);return 0;}MaxLoading(weight,n,bestx,c1);cout装载序列为; for(int i0;in;i){coutbestx[i] ;}coutendl;cout第1艘船的最优装载量为MaxLoading(weight,n,bestx,c1)endl;cout装载的货物为;for(int i0;in;i){if(bestx[i]!0)coutweight[i] ;}coutendl;cout第2艘船的最优装载量为sumweight-MaxLoading(weight,n,bestx,c1)endl;cout装载的货物为;for(int i0;in;i){if(bestx[i]!1)coutweight[i] ;}} 堆写法
#includeiostream
#includequeue//优先队列的头文件
using namespace std;class bbnode{ public:bbnode *parent;//指向父节点的指针 bool Lchild;//是否是左孩子结点的标记
};
//优先队列中节点的定义
class HeapNode{public:operator double() const{return uweight;}int operator (HeapNode hn) const{return uweighthn.uweight; }int operator (HeapNode hn) const{return uweighthn.uweight; }int operator (HeapNode hn) const{return uweighthn.uweight; }int operator (HeapNode hn) const{return uweighthn.uweight; }int operator (HeapNode hn) const{return uweighthn.uweight; }HeapNode(){}bbnode *ptr; //指向活结点在子集树中相应节点的指针int uweight; //活结点的优先级(上界) //优先级的定义从根节点到节点x的路径相应的载重量加上剩余集装箱的重量之和int level; //活结点在子集树中所处的层次
};
class MaxHeap
{
public:MaxHeap(int n); //构造函数N表示堆中能存储的最大元素的个数 void Insert(HeapNode heapNode); //向堆中插入一个结点 void DeleteMax(HeapNode heapNode); //删除堆中的最大结点
private:int size; HeapNode *MH; void Delete(HeapNode heapNode,int index); //删除堆中标号为index的元素index从1开始即1表示最大元素 void SiftUp(int index); //将堆中标号为index的元素向上调整保证堆结构 void SiftDown(int index); //将堆中标号为index的元素向下调整保证堆结构
};MaxHeap::MaxHeap(int n)
{size0;MHnew HeapNode[n];
}void MaxHeap::SiftUp(int index)
{if(index1)return;bool donefalse;do{if(MH[index]MH[index/2]){HeapNode tmpMH[index];MH[index]MH[index/2];MH[index/2]tmp;}elsedonetrue;indexindex/2;}while(index1!done);
}void MaxHeap::SiftDown(int index)
{if(2*indexsize)return;bool donefalse;do{index2*index;if(index1sizeMH[index1]MH[index])indexindex1;if(MH[index/2]MH[index]){HeapNode tmpMH[index];MH[index]MH[index/2];MH[index/2]tmp;}elsedonetrue;}while(2*indexsize!done);
}void MaxHeap::Insert(HeapNode heapNode)
{size1;MH[size]heapNode;SiftUp(size);
}void MaxHeap::Delete(HeapNode heapNode,int index)
{if(index1||indexsize){return;}HeapNode xMH[index],yMH[size];heapNodeMH[index];size-1;if(indexsize1)return;MH[index]y;//将原来堆中的最后一个放到要被删除的位置再继续调整堆 if(yx)SiftUp(index);elseSiftDown(index);
}void MaxHeap::DeleteMax(HeapNode heapNode)
{Delete(heapNode,1);
}
//子集树中节点的定义//该函数是将新产生的活结点加入到子集树中并将这个节点插入到表示活结点优先队列的最大堆中
void AddLiveNode(MaxHeap Q,bbnode *parent,bool isLeft,int uWeight,int level)
{//先在子集树中建立这个节点bbnode *b new bbnode;b-parent parent;b-Lchild isLeft;//再在优先队列中新建一个节点HeapNode H;H.ptr b;//将刚在添加到子集树中的新节点b再赋值给将要添加到优先队列中的节点h H.uweight uWeight;H.level level; //将新建的节点添加到优先队列Q.Insert(H); }int MaxLoading(int *weight,int n,int *bestx,int c)
{MaxHeap *Maxhpnew MaxHeap(100);;int i0;// 表示当前所在子集树的层次int now_weight0;//表示当前已装载的重量int node_priority0; //优先级————装载的最大上界当前装载量剩余集装箱的重量HeapNode H;//用于保存从优先队列出来的节点 bbnode *B;//子集树上的扩展节点int *remains; //剩余集装箱 记载未装的货物remains new int[n];remains[n-1]0;//当到达最后的叶子节点时没有剩余的货物 for(int jn-2;j0;j--){ //计算当到达指定层时的剩余数组 remains[j]remains[j1]weight[j1];}while(i!n)//没有到达叶子节点时 ,到达第i层 {if(now_weightweight[i]c)//即当前的重量能够装的下 进入左子树 左孩子 {node_priority(now_weightweight[i]) remains[i];//优先级 当前装载量剩余集装箱的重量AddLiveNode(*Maxhp,B,true,node_priority,i1);}// 进入右子树 右孩子 node_priority(now_weight) remains[i];//优先级 当前装载量剩余集装箱的重量AddLiveNode(*Maxhp,B,false,node_priority,i1);Maxhp-DeleteMax(H); //查询优先队列队头结点 iH.level;BH.ptr; //记录当前到达的结点 now_weightH.uweight - remains[i-1]; //计算当前已经装载量 }// 记录已装载货物 for(int jn-1;j0;j--){bestx[j]B-Lchild? 1:0;BB-parent;}return now_weight; //返回最优装载量 }
int main()
{int n; //货物数 int shipNum; //货船数量 int bestw; //最优装载量 int weight[n]; //货物总重量 int bestx[n]; //最优的装载序列 int c10; //第一艘船的装载重量 int c20; //第二艘船的装载重量 cout请输入货物数;cinn;cout请输入货船的数量;cinshipNum;cout请输入货物的重量序列;for(int i0;in;i){cinweight[i];}cout请输入两艘船的载重量;cinc1c2;int maxc0;//船的最大装载重量 int sumcc1c2;//船的装载重和 if(c1c2)maxcc1;else maxcc2;int maxweight0;//货物中的最大重量int sumweight0; //货船总重量 for(int i0;in;i){if(weight[i]maxweight){maxweightweight[i];}sumweightweight[i];}if(maxweightmaxc){printf(货物重量超过货船的载重量无法装载);return 0;} if(sumweightsumc){printf(货物总重量超过货船的总载重量无法装载);return 0;}MaxLoading(weight,n,bestx,c1);cout装载序列为; for(int i0;in;i){coutbestx[i] ;}coutendl;cout第1艘船的最优装载量为MaxLoading(weight,n,bestx,c1)endl;cout装载的货物为;for(int i0;in;i){if(bestx[i]!0)coutweight[i] ;}coutendl;cout第2艘船的最优装载量为sumweight-MaxLoading(weight,n,bestx,c1)endl;cout装载的货物为;for(int i0;in;i){if(bestx[i]!1)coutweight[i] ;}}
