C++——《算法分析与设计》实验报告——箱子装载问题
生活随笔
收集整理的這篇文章主要介紹了
C++——《算法分析与设计》实验报告——箱子装载问题
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
| 實驗名稱: 箱子裝載問題 | 實驗地點： |
| 實驗目的： 1、 理解和復習所學各種算法的概念； 2、? 掌握和復習所學各種算法的基本要素； 3、? 掌握各種算法的優(yōu)點和區(qū)別； 4、? 通過應用范例掌握選擇最佳算法的設計技巧與策略； ? | |
| 實驗原理 回溯法原理： 從開始結(jié)點出發(fā)，以深度優(yōu)先方式搜索整個解空間。這個節(jié)點成為活結(jié)點，同時也成為當前的擴展節(jié)點。在當前的擴展節(jié)點處，搜索向縱深方向一致一個新節(jié)點。 貪心算法原理： 貪心算法通過一系列的選擇來得到問題的解。他所做的每一個選擇都是當前狀態(tài)下局部最好選擇，即貪心選擇。 分支限界法原理： 每一個活結(jié)點只有一次機會成為擴展結(jié)點，一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。兒子結(jié)點中，導致不可行解或者非最優(yōu)解的被舍棄，其余加入活結(jié)點表中。從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復上述結(jié)點的擴展過程，一直持續(xù)到找到所需的解或活結(jié)點表為空為止。 | |
| 實驗內(nèi)容： 1、使用貪心算法、回溯法、分支限界法解決箱子裝載問題。（任選兩種） 2、通過上機實驗進行算法實現(xiàn)。 3、保存和打印出程序的運行結(jié)果，并結(jié)合程序進行分析，上交實驗報告。 | |
| 源程序： （1）貪心算法 #include<stdio.h> #include<stdlib.h> void swap(int &x, int &y){ //交換 int t;t = x;x = y;y = t; } void sort(int w[], int t[], int n) //排序，有小到大 {for (int m = 0; m<n; m++) //為每個物品編序號 t[m] = m;int i, j;int lastExchangeIndex;i = n - 1;while (i>0){lastExchangeIndex = 0;for (j = 0; j<i; j++){if (w[j + 1]<w[j]){swap(w[j + 1], w[j]); //物品的重量交換lastExchangeIndex = j;swap(t[j], t[j + 1]);}}i = lastExchangeIndex;} } void loading(int x[], int w[], int c, int n, int *t) //最有裝載 {sort(w, t, n);for (int i = 0; i<n; i++)x[i] = 0;for (int j = 0; j<n&&w[t[j]] <= c; j++){x[t[j]] = 1;c -= w[t[j]]; //裝入 } } int main(){int n, c;printf("請輸入物品個數(shù)：");scanf("%d", &n);printf("請輸入最大容量：");scanf("%d", &c);int x[200]; //存儲物品編號 int w[200]; //存儲每個物品重量for (int i = 0; i<n; i++){printf("請輸入第%d個物品重量：", i);scanf("%d", &w[i]);}int *t = new int[n]; //物品是否裝入for (int j = 0; j<n; j++)x[j] = 0; //初始化物品均未裝入loading(x, w, c, n, t);printf("裝入物品編號為：");for (int k = 0; k<n; k++)if (x[k] == 1)printf("%d ", t[k]);return 0;}（2）回溯法 #include<stdio.h> #include<stdlib.h> #define num 100 int bestx[num] = { 0 }; //存放最優(yōu)解 int w[num]; //集裝箱重量 int x[num]; //解 int bestw = 0; //最優(yōu)裝船重量 int cw = 0; //當前已裝船重量 int n; //集裝箱個數(shù) int c1; //第一船的重量 int c2; //第二船的重量//限界函數(shù) int bound(int t) // 選擇當前節(jié)點又分支的剩余集裝箱重之和 {int rw = 0;for (int i = t + 1; t<n; t++)rw = rw + w[i];return (rw + cw); //上界 } //遞歸求解 void loadingRec(int t){int i;if (t>n) //到底葉子節(jié)點，求得一個可行解{if (cw>bestw){ //當前解比以前解更優(yōu) bestw = cw;for (i = 1; i <= n; i++)bestx[i] = x[i];};return;}else{if (cw + w[t]<c1) //左分支滿足約束條件{x[t] = 1;cw = cw + w[t];loadingRec(t + 1); //前進繼續(xù)搜索下一節(jié)點//回溯；回復cw與x[t]的值cw = cw - w[t];x[t] = 0;}if (bound(t)>bestw) //右分支滿足限界條件loadingRec(t + 1);} } int main(){n = 4; //集裝箱個數(shù)printf("集裝箱個數(shù):");scanf("%d",&n); printf("集裝箱重量:");w[1] = 4, w[2] = 5, w[3] = 3, w[4] = 2; //集裝箱重量for(int i=1;i<=n;i++){scanf("%d",&w[i]);}c1 = 8; //第一個船重量c2 = 7; //第二個船重量printf("第一個船重量:");scanf("%d",&c1);printf("第二個船重量:"); scanf("%d",&c2); cw = 0;bestw = 0;loadingRec(1); //從第一個集裝箱開始裝箱printf("第一船的最優(yōu)裝載量為：%d\n", bestw);printf("第一船的最優(yōu)解為");for (int i = 1; i <= n; i++)printf("%d ", bestx[i]);//求剩余集裝箱的重量int cw2 = 0;for (int i = 0; i <= n; i++)if (bestx[i] == 0)cw2 += w[i];if (cw2>c2)printf("無法將剩余集裝箱轉(zhuǎn)入第二船，問題無解");elseprintf("可以將剩余集裝箱裝入第二船，問題有解");getchar(); }（3）分支限界法 #include <iostream> #include <stdio.h> #include <stdlib.h> #include<queue> #define num 100 float w[num]; //集裝箱重量 int x[num]; //解 float c; int n; //集裝箱個數(shù) float bestw; using namespace std; template<class Type> class HeapNode; template<class Type> class bbnode; template<class Type> void AddLiveNode(priority_queue<HeapNode<Type> > &H,bbnode<Type> *E,Type wt,bool ch,int lev); template<class Type> Type MaxLoading(Type w[],Type c,int n,int bestx[]); template<class Type> class bbnode {friend void AddLiveNode<Type>(priority_queue<HeapNode<Type> > &H,bbnode<Type> *E,Type wt,bool ch,int lev);friend Type MaxLoading<Type>(Type*,Type,int,int*);friend class AdjacencyGraph;//鄰接矩陣public:bbnode<Type> *parent;//指向父節(jié)點的指針bool Lchild;//左兒子結(jié)點標志 }; template<class Type> class HeapNode {friend void AddLiveNode<Type>(priority_queue<HeapNode<Type> > &H,bbnode<Type> *E,Type wt,bool ch,int lev);friend Type MaxLoading<Type>(Type *,Type,int,int*);public:operator Type () const{return uweight;}public:bbnode<Type> *ptr;//指向活結(jié)點在子集樹中相應結(jié)點的指針Type uweight;//活結(jié)點優(yōu)先級(上界)int level;//活結(jié)點在子集樹中所處的層序號 }; //將活結(jié)點加入到表示活結(jié)點優(yōu)先隊列的最大堆H中 template<class Type> void AddLiveNode(priority_queue<HeapNode<Type> > &H,bbnode<Type> *E,Type wt,bool ch,int lev) {bbnode<Type> *b = new bbnode<Type> ;b->parent = E;b->Lchild = ch;HeapNode<Type>N;N.ptr = b;N.uweight = wt;N.level = lev;H.push(N); } //優(yōu)先隊列式分支限界法,返回最優(yōu)載重量,bestx返回最優(yōu)解 //優(yōu)先級是當前載重量+剩余重量 template<class Type> Type MaxLoading(Type w[],Type c,int n,int bestx[]) {priority_queue<HeapNode<Type> > H;//定義最大堆的容量為1000Type *r = new Type [n+1];//剩余重量r[n] = 0;for(int j = n - 1;j > 0;j--){r[j] = r[j+1] + w[j+1];}//初始化int i = 1;//當前擴展結(jié)點所在的層bbnode <Type> *E = 0;//當前擴展結(jié)點Type Ew = 0;//擴展結(jié)點所相應的載重量//搜索子集空間樹while(i != n + 1)//非葉子節(jié)點{//檢查當前擴展結(jié)點的兒子節(jié)點if(Ew+w[i] <= c){AddLiveNode(H,E,Ew+w[i]+r[i],true,i+1);//左兒子結(jié)點為可行結(jié)點}AddLiveNode(H,E,Ew+r[i],false,i+1);//右兒子結(jié)點HeapNode<Type>N =H.top();//取下一擴展結(jié)點H.pop();//下一擴展結(jié)點,將最大值刪去i = N.level;E = N.ptr;Ew = N.uweight - r[i-1];//當前優(yōu)先級為上一優(yōu)先級-上一結(jié)點重量}//構(gòu)造當前最優(yōu)解,類似回溯的過程for(int j = n;j > 0;j--){bestx[j] = E->Lchild;E = E->parent;}return Ew; } int main(){printf("輪船重量:");scanf("%f",&c);printf("請輸入物品個數(shù)：");scanf("%d", &n);printf("物品的重量:");for(int i=1;i<=n;i++){scanf("%f",&w[i]);}bestw=MaxLoading<float>(w,c,n,x);cout<<"分支限界選擇結(jié)果為："<<endl;for(int i=1;i<=n;i++){cout<<x[i]<<" ";}cout<<endl;cout<<"最優(yōu)裝載重量為："<<bestw<<endl;return 0; }? | |
| 實驗結(jié)果： （1）貪心算法 ? 貪心算法并沒有求得最優(yōu)解。 （2）回溯法 （3）分支限界法 ? | |
| 心得與體會： 1、 理解和復習貪心算法、回溯法、分支限界法的概念； 2、? 掌握和復習貪心算法、回溯法、分支限界法的基本要素； 3、? 掌握貪心算法、回溯法、分支限界法的優(yōu)點和區(qū)別； 4、? 通過應用范例掌握選擇最佳算法的設計技巧與策略； ? | |
參考文章
https://blog.csdn.net/qq_43496675/article/details/106090334
https://blog.csdn.net/weixin_36888577/article/details/79937886
https://blog.csdn.net/weixin_44755413/article/details/106199259
https://blog.csdn.net/softwareldu/article/details/41170137
https://blog.csdn.net/xiaoquantouer/article/details/52015928
總結(jié)
以上是生活随笔為你收集整理的C++——《算法分析与设计》实验报告——箱子装载问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： MySQL——Access|SQL Se
- 下一篇： 《IBM-PC汇编语言程序设计》(第2版