2016/2017(2）
实验题目装载问题5种解法
学生姓名 学生学号 学生班级 任课教师 提交日期2017
计算机科学与技术学
目录
一问题定义 ........................................................................................................................................2 二解决方案 ........................................................................................................................................2
1优先队列式分支限界法求解 ..................................................................................................2
1.1算法分析 ......................................................................................................................2 1.2代码 ..............................................................................................................................2 1。3运行结果 ................................................................................................................ 12 2队列式分支限界法求解....................................................................................................... 12
2。1算法分析 ................................................................................................................ 12 2。2代码 ........................................................................................................................ 13 2.3测试截图 ................................................................................................................... 21 3回朔法-迭代 ......................................................................................................................... 21
3.1算法分析 ................................................................................................................... 21 3。2代码 ........................................................................................................................ 21 3.3测试截图 ....................................................................................................................25 4回朔法-递归 ..........................................................................................................................25
4。1算法分析 .................................................................................................................25 4。2代码 .........................................................................................................................25 4.3测试截图 ................................................................................................................... 30 5贪心算法 .............................................................................................................................. 30
5.1算法分析 ................................................................................................................... 30 5.2代码 ........................................................................................................................... 30 5。3测试截图 ................................................................................................................ 33
算法分析与设计
一问题定义
有一批共有 n 个集装箱要装上两艘载重量分别为 c1 和 c2 的轮船，其中集装箱 i 的重量为 w［i]， 且重量之和小于(c1 + c2）。装载问题要求确定是否存在一个合理的装载方案可将这 n 个集装箱装上这两艘轮船。如果有，找出一种装载方案.
二解决方案
1优先队列式分支限界法求解 1.1算法分析
活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点.以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点,则可以断言该叶结点所相应的解即为最优解。此时可终止算法.
1.2代码
1。2-1////MaxHeap.h
template MaxHeap(int MaxHeapSize = 10）; ~MaxHeap() {delete [］ heap;｝ int Size() const {return CurrentSize;} 2 / 33 算法分析与设计 T Max（) { //查找 if (CurrentSize == 0) ｛ throw OutOfBounds（)； } return heap[1]; ｝ MaxHeap void Initialize(T a［]， int size, int private: int CurrentSize， MaxSize； T ＊heap； // element array ｝; template template MaxHeap 3 / 33 ArraySize）; 算法分析与设计 if (CurrentSize == MaxSize） ｛ cout〈<\"no space！\"〈〈endl； return *this； ｝ // 寻找新元素x的位置 // i——初始为新叶节点的位置，逐层向上，寻找最终位置 int i = ++CurrentSize; while (i ！= 1 ＆＆ x > heap［i/2]） ｛ // i不是根节点，且其值大于父节点的值，需要继续调整 heap[i］ = heap[i/2]; // 父节点下降 i /= 2; // 继续向上，搜寻正确位置 } heap［i] = x； return ＊this; ｝ template MaxHeap cout〈<\"Empty heap！\"< 算法分析与设计 x = heap[1］； // 删除最大元素 // 重整堆 T y = heap［CurrentSize-—］; // 取最后一个节点，从根开始重整 // find place for y starting at root int i = 1, // current node of heap ci = 2; // child of i while (ci <= CurrentSize) { // 使ci指向i的两个孩子中较大者 if (ci < CurrentSize && heap[ci] 〈 heap［ci+1]） { ci++; ｝ // y的值大于等于孩子节点吗？ if (y >= heap［ci]) { break； // 是，i就是y的正确位置,退出 } // 否，需要继续向下,重整堆 heap［i］ = heap[ci]； // 大于父节点的孩子节点上升 i = ci; // 向下一层，继续搜索正确位置 ci *= 2； } heap［i] = y; 5 / 33 算法分析与设计 return *this； ｝ template〈class T> void MaxHeap CurrentSize = size； MaxSize = ArraySize； // 从最后一个内部节点开始，一直到根，对每个子树进行堆重整 for （int i = CurrentSize/2; i 〉= 1； i--） ｛ T y = heap[i］； // 子树根节点元素 // find place to put y int c = 2*i； // parent of c is target // location for y while （c <= CurrentSize） { // heap[c] should be larger sibling if （c < CurrentSize ＆＆ heap[c] ［c+1]) { c++; ｝ // can we put y in heap[c/2]? if （y 〉= heap[c］） ｛ break; // yes 6 / 33 < heap 算法分析与设计 } // no heap［c/2］ = heap［c］; // move child up c *= 2； // move down a level ｝ heap［c/2] = y; ｝ } 1.2—2///6d3-2.cpp //装载问题 优先队列式分支限界法求解 ＃include \"stdafx.h\" ＃include ”MaxHeap。h” ＃include 〈iostream> using namespace std; const int N = 4; class bbnode； template〈class Type〉 class HeapNode { template friend Type MaxLoading（Type w［］,Type c,int n,int bestx[］）； 7 / 33 ＊ 算法分析与设计 public: operator Type（） const{return uweight；} private: bbnode *ptr; //指向活节点在子集树中相应节点的指针 Type uweight； //活节点优先级（上界) int level; //活节点在子集树中所处的层序号 ｝； class bbnode { template〈class Type〉 friend void AddLiveNode（MaxHeap〈HeapNode friend Type MaxLoading（Type w［］,Type c,int n，int bestx[］）; friend class AdjacencyGraph; private: bbnode *parent； //指向父节点的指针 bool LChild； //左儿子节点标识 }； template void AddLiveNode(MaxHeap〈HeapNode〈Type〉〉＆ H,bbnode ＊E,Type wt，bool ch,int lev)； template 8 / 33 算法分析与设计 int main(） ｛ float c = 70； float w[] = {0，20,10，26，15｝;//下标从1开始 int x［N+1]； float bestw； cout<<\"轮船载重为：\"<〈c〈〈endl; cout<〈\"待装物品的重量分别为：\"<〈endl; for（int i=1； i<=N; i++） { cout< bestw = MaxLoading(w，c,N，x）； cout<〈”分支限界选择结果为：”<〈endl； for(int i=1; i〈=4； i++） ｛ cout<〈x[i]<〈” \"; ｝ cout< //将活节点加入到表示活节点优先队列的最大堆H中 9 / 33 算法分析与设计 template〈class Type> void AddLiveNode(MaxHeap bbnode ＊b = new bbnode; b—〉parent = E; b—>LChild = ch； HeapNode〈Type〉 N； N。uweight = wt； N.level = lev； N.ptr = b; H。Insert(N); ｝ //优先队列式分支限界法，返回最优载重量,bestx返回最优解 template〈class Type> Type MaxLoading（Type w[],Type c，int n,int bestx［]） ｛ //定义最大的容量为1000 MaxHeap〈HeapNode〈Type〉> H（1000）; //定义剩余容量数组 Type ＊r = new Type［n+1］; r［n] = 0； for(int j=n-1; j>0； j—-) ｛ r[j］ = r[j+1] + w[j+1］; } 10 / 33 ，bbnode *E， 算法分析与设计 //初始化 int i = 1;//当前扩展节点所处的层 bbnode ＊E = 0；//当前扩展节点 Type Ew = 0; //扩展节点所相应的载重量 //搜索子集空间树 while(i!=n+1）//非叶子节点 { //检查当前扩展节点的儿子节点 if(Ew+w［i］<=c) ｛ AddLiveNode（H，E，Ew+w［i]+r[i］，true，i+1); ｝ //右儿子节点 AddLiveNode（H,E,Ew+r［i］,false，i+1）; //取下一扩展节点 HeapNode〈Type> N； H.DeleteMax(N);//非空 i = N.level； E = N.ptr； Ew = N。uweight - r[i—1］； } //构造当前最优解 for(int j=n; j〉0; j—-) { bestx［j] = E—>LChild; E = E-〉parent; 11 / 33 算法分析与设计 } return Ew; } 1。3运行结果 2队列式分支限界法求解 2。1算法分析 在算法的循环体中，首先检测当前扩展结点的左儿子结点是否为可行结点.如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中（右儿子结点一定是可行结点）.2个儿子结点都产生后，当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记—1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空.如果队列非空,则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点. 节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船.设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+r 12 / 33 2。2代码 22-1////Queue。h ＃include〈iostream> using namespace std； template 〈class T〉 class Queue ｛ public: Queue(int MaxQueueSize=50）； ~Queue（)｛delete [] queue；｝ bool IsEmpty()const{return front==rear;｝ bool IsFull( {return （ ( (rear+1）%MaxSize==front )?1:0);｝ T Top() const； T Last（） const； Queue int front； int rear; int MaxSize； T ＊queue; }； template〈class T〉 13 / 33 算法分析与设计 ） 算法分析与设计 Queue template if（IsEmpty(）） { cout〈〈”queue:no element，no!\"〈〈endl; return 0; ｝ else return queue[（front+1） % MaxSize]; } template〈class T〉 T Queue〈T〉 ：:Last()const { if（IsEmpty()） { cout〈<\"queue：no element”〈 template〈class T〉 14 / 33 算法分析与设计 Queue〈T>& Queue〈T>::Add(const T＆ x） ｛ if（IsFull(））cout<<”queue:no memory\"< return *this; ｝ template Queue if（IsFull(）)cout〈〈”queue：no memory\"〈〈endl； else ｛ front=(front+MaxSize-1)％ MaxSize； queue[（front+1）% MaxSize］=x; ｝ return *this； } template 15 / 33 x=queue[front］; } return *this; ｝ template〈class T> void Queue ostream& operator 〈< （ostream＆ out，const Queue〈T〉＆｛x.Output（out)；return out；｝ 2。2—2////6d3-1.cpp //装载问题 队列式分支限界法求解 #include \"stdafx.h” ＃include \"Queue.h” ＃include template 算法分析与设计 x） 算法分析与设计 template template〈class Type〉 friend Type MaxLoading（Type w[],Type c,int n,int bestx［]）; private： QNode *parent； //指向父节点的指针 bool LChild； //左儿子标识 Type weight； //节点所相应的载重量 }； template〈class Type> void EnQueue（Queue〈QNode〈Type〉＊>＆Q,Type wt，int i，int n,Type bestw,QNode〈Type〉＊E，QNode〈Type> *＆bestE，int bestx[］，bool ch); template Type MaxLoading(Type w[］，Type c，int n,int bestx[］)； int main（） { float c = 70; float w[] = ｛0,20，10，26，15};//下标从1开始 int x［N+1］; float bestw； cout〈〈”轮船载重为：”< 算法分析与设计 for(int i=1； i<=N; i++） ｛ cout〈〈w[i]<<\" \"； } cout< cout〈<”分支限界选择结果为:”<〈endl; for（int i=1; i<=4; i++） ｛ cout< cout〈〈\"最优装载重量为：”< //将活节点加入到活节点队列Q中 template if(i == n)//可行叶节点 { if（wt == bestw) { //当前最优装载重量 bestE = E； bestx［n］ = ch; 18 / 33 bestw，算法分析与设计 ｝ return； ｝ //非叶节点 QNode template Queue〈QNode Q。Add(0）; //同层节点尾部标识 int i = 1； //当前扩展节点所处的层 Type Ew = 0， //扩展节点所相应的载重量 bestw = 0， //当前最优装载重量 r = 0; //剩余集装箱重量 for(int j=2; j<=n； j++） { r += w［j］; ｝ QNode 19 / 33 算法分析与设计 //搜索子集空间树 while(true) ｛ //检查左儿子节点 Type wt = Ew + w［i]; if(wt <= c)//可行节点 ｛ if(wt>bestw) ｛ bestw = wt; ｝ EnQueue(Q，wt,i，n，bestw，E,bestE,bestx,true）; ｝ //检查右儿子节点 if（Ew+r〉bestw） { EnQueue(Q，Ew,i,n，bestw，E，bestE，bestx,false）； ｝ Q.Delete(E）；//取下一扩展节点 if（！E）//同层节点尾部 ｛ if(Q。IsEmpty（)) ｛ break； } Q.Add(0)； //同层节点尾部标识 Q.Delete（E）； //取下一扩展节点 i++； //进入下一层 r-=w[i]； //剩余集装箱重量 20 / 33 算法分析与设计 } Ew =E—〉weight; //新扩展节点所对应的载重量 ｝ //构造当前最优解 for（int j=n—1; j〉0； j--） ｛ bestx[j］ = bestE—>LChild; bestE = bestE-〉parent； ｝ return bestw； ｝ 2.3测试截图 3回朔法—迭代 3.1算法分析 用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。可行性约束条件重量之和小于(c1 + c2）可剪去不满足约束条件的子树用cw记当前的装载重量，即cw=（w1x1+w2x2+...+wjxj),当cw〉c1时，以节点Z为根的子树中所有节点都不满足约束条件,因而该子树中解均为不可行解，故可将该子树剪去。 3。2代码 ＃include 〈iostream〉 using namespace std; template〈class Type〉 Type MaxLoading(Type w［ ], Type c, int n, int bestx［ ]); int main() 21 / 33 算法分析与设计 { int n=3,m； int c=50，c2=50; int w[4]=｛0,10，40,40}； int bestx[4]; m=MaxLoading(w, c， n， bestx）; cout〈〈”轮船的载重量分别为：”〈 cout〈 cout〈〈”回溯选择结果为：”〈〈endl； cout<<\"m(1)=\"〈〈m<〈endl; cout<〈\"x(i)=”; for (int i=1;i〈=n；i++) ｛ cout< 22 / 33 算法分析与设计 for （int j=1;j<=n；j++) ｛ m2=m2+w［j］*(1-bestx[j］)； } cout<〈”m(2）=\"〈 cout<<\"因为m(2)大于c（2），所以原问题无解!\"< template 〈class Type〉 Type MaxLoading(Type w[]，Type c,int n，int bestx[］)//迭代回溯法,返回最优载重量及其相应解，初始化根结点 ｛ int i=1；//当前层，x[1:i—1］为当前路径 int ＊x=new int[n+1]； Type bestw=0， //当前最优载重量 cw=0， //当前载重量 r=0; //剩余集装箱重量 for (int j=1；j〈=n；j++） ｛ r+=w[j］; ｝ while(true）//搜索子树 23 / 33 算法分析与设计 { while(i<=n &&cw+w［i]〈=c)//进入左子树 { r—=w[i］; cw+=w[i]; x［i]=1; i++； ｝ if （i>n）//到达叶结点 { for (int j=1；j<=n;j++） ｛ bestx[j］=x[j］； } bestw=cw； ｝ else//进入右子树 { r-=w[i]; x[i］=0; i++； ｝ while （cw+r<=bestw） { //剪枝回溯 i——； while (i〉0 && ！x[i］） { r+=w［i］； i——; ｝ //从右子树返回 if （i==0） ｛ 24 / 33 算法分析与设计 delete ［]x； return bestw； } x[i］=0； cw—=w[i]； i++; ｝ } ｝ 3。3测试截图 4回朔法—递归 4.1算法分析 与回朔法-迭代的相同，以下代码只是更改了具体的实现过程 4。2代码 #include 〈iostream> using namespace std； template 〈class Type〉 class Loading { //friend Type MaxLoading（Type[］,Type，int,int //private： public: void Backtrack（int i)； int n， //集装箱数 25 / 33 []); 算法分析与设计 ＊x， //当前解 *bestx； //当前最优解 Type ＊w, //集装箱重量数组 c， //第一艘轮船的载重量 cw, //当前载重量 bestw， //当前最优载重量 r; //剩余集装箱重量 }； template 〈class Type> void Loading template Type MaxLoading（Type w[］, Type c， int n, int bestx[]）; int main(） { int n=3，m； int c=50，c2=50; int w［4］=｛0，10,40，40｝； int bestx[4]; m=MaxLoading（w, c， n， bestx)； cout〈<\"轮船的载重量分别为：\"<〈endl； cout<〈”c(1)=\"〈〈c〈<”，c（2）=\"〈〈c2〈〈endl; cout<〈”待装集装箱重量分别为:”〈〈endl; cout〈<\"w（i)=”； 26 / 33 算法分析与设计 for (int i=1；i〈=n；i++） ｛ cout< cout〈〈bestx［i]〈〈” ”； ｝ cout< for (int j=1;j〈=n；j++） { m2=m2+w［j］*（1—bestx[j］); ｝ cout<〈”m（2)=”〈〈m2<〈endl； if（m2>c2) { cout<〈”因为m(2)大于c（2），所以原问题无解！\"<〈endl； } return 0; } 27 / 33 算法分析与设计 template 〈class Type> void Loading if （i > n）// 到达叶结点 { if （cw〉bestw） { for(int j=1；j〈=n;j++） ｛ bestx[j］=x[j];//更新最优解 bestw=cw； } } return； } r—=w[i]； if （cw + w[i] <= c） // 搜索左子树 { x［i］ = 1; cw += w［i］； Backtrack(i+1)； cw-=w[i]; ｝ if (cw + r > bestw） { x[i] = 0； // 搜索右子树 Backtrack(i + 1)； } 28 / 33 算法分析与设计 r+=w［i]; } template Loading〈Type>X; //初始化X X.x=new int[n+1］; X。w=w; X.c=c； X.n=n; X.bestx=bestx; X.bestw=0; X.cw=0; //初始化r X.r=0; for (int i=1;i〈=n;i++) { X。r+=w［i］; ｝ X.Backtrack（1); delete []X.x; return X。bestw; } 29 / 33 算法分析与设计 4。3测试截图 5贪心算法 5。1算法分析 最优子结构性质：设(x1,x2,……xn)是最优装载问题的满足贪心选择性质的最优解，则易知,x1=1，(x2，x3,……xn）是轮船载重量为c—w1，待装船集装箱为{2，3，……n}时相应最优装载问题的最优解。因此，最优装载问题具有最优子结构性质。 求解过程：最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。 5.2代码 #include template template void Loading(int x[］, Type w［], Type c, int n)； template void SelectSort（Type w［］,int *t，int n); int main（） { 30 / 33 算法分析与设计 float c = 70; float w[] = {0,20，10,26,15｝;//下标从1开始 int x［N+1]; cout〈〈\"轮船载重为：”<〈c< cout〈 cout< return 0； ｝ template int *t = new int [n+1］；//存储排完序后w[］的原始索引 SelectSort（w, t, n）； for(int i=1； i〈=n; i++) 31 / 33 算法分析与设计 { x[i] = 0;//初始化数组x[] } for（int i=1； i〈=n &＆ w［t[i]]<=c; i++) { x[t[i］］ = 1； c -= w[t［i]］； } } template void SelectSort(Type w[]，int *t，int n） ｛ Type tempArray[N+1］，temp; memcpy(tempArray，w,(n+1）*sizeof(Type)）；//将w拷贝到临时数组tempArray中 int min; for(int i=1；i〈=n;i++) { t[i］ = i； } for（int i=1;i for(int j=i+1;j〈=n;j++) { if（tempArray［min］>tempArray［j］） { 32 / 33 算法分析与设计 min=j； ｝ ｝ Swap（tempArray[i］,tempArray[min］）； Swap（t[i］,t[min])； ｝ ｝ template Type temp = x； x = y; y = temp; } 5.3测试截图 ＆y） 33 / 33 因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- awee.cn 版权所有 湘ICP备2023022495号-5
违法及侵权请联系：TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务