实验五 箱子装载问题（分支限界法）

实验五 箱子装载问题

一、实验目的：

1、 理解和复习所学各种算法的概念； 2、 掌握和复习所学各种算法的基本要素； 3、 掌握各种算法的优点和区别；

4、 通过应用范例掌握选择最佳算法的设计技巧与策略；

二、实验内容及要求：

1、使用贪心算法、回溯法、分支限界法解决箱子装载问题。（任选两种） 2、通过上机实验进行算法实现。

3、保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。

三、实验原理：

回溯法原理：

从开始结点出发，以深度优先方式搜索整个解空间。这个节点成为活结点，同时也成为当前的扩展节点。在当前的扩展节点处，搜索向纵深方向一致一个新节点。 贪心算法原理：

贪心算法通过一系列的选择来得到问题的解。他所做的每一个选择都是当前状态下局部

最好选择，即贪心选择。

四、程序代码：

贪心算法：

#include #include #define N 100

using namespace std; int main(){

int t[N],w0[N],w[N],n,c,m,i,j;

int max=0,weight=0; bool tx[N];

cout<<\请输入轮船的载重量c：\ cin>>c;

cout<<\请输入可以装入的集装箱的数目n：\ cin>>n;

cout<<\请输入各集装箱的重量w[i](1<=i<=n)：\ for(int i=0;i>w0[i]; w[i+1]=w0[i];

tx[i+1]=false; }

for(i=1;iw[j]) { int tem; tem=w[j];

w[j]=w[i];

w[i]=tem; } } }

for(i=1;i<=n;i++)printf(\ printf(\

for(i=1;i<=n;i++){

int min=weight+w[i]; if(min<=c){ weight+=w[i]; tx[i]=true; } }

m=i-1;

cout<<\最优装载情况为：\ cout<<\装入轮船的集装箱为：\ max=0;

for(i=1;i<=m;i++){

if(tx[i]){max+=w[i];cout<

cout<

cout<<\装入的集装箱的最大重量为：\ system(\ } 回溯法：

#include using namespace std;

class Loading

{

friend float MaxLoading(float[],float,int);

public:

void Backtrack(int i); int n;

int *x,*bestx;

float *w,c,cw,bestw,r; };

float Maxloading(float w1[],float c1,float c2,int n1,int bestx1[]) {

Loading k; int j;

float MAXLoad;

k.x= new int [n1+1]; k.bestx=bestx1; k.w = w1; k.c = c1; k.n = n1; k.cw = 0;

k.bestw = 0; k.r = 0;

for(int i=1;i<=n1;i++) k.r+=w1[i]; k.Backtrack(1); delete [] k.x;

cout<<\船1最优装载：\ MAXLoad=k.bestw; for( j=1;j<=n1;j++) {

if(k.bestx[j]==0) {

MAXLoad+=w1[j]; c2-=w1[j]; if(c2<0) {

cout<<\找不到合理装载方案！\ return -1; } }

}

cout<<\船1中的箱子：\

for( j=1;j<=n1;j++) if(k.bestx[j]==1) cout<

cout<<\船2中的箱子：\ for( j=1;j<=n1;j++) if(k.bestx[j]==0) cout<

void Loading::Backtrack(int i) { 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); }

r+=w[i]; }

int main() {

float w[20]; float c1,c2,k; int n,bestx[20];

cout<<\输入箱子数：\ cin>>n;

cout<<\输入箱子重量：\ for(int i=1;i<=n;i++) cin>>w[i];

cout<<\输入容量船1，船2：\ cin>>c1>>c2;

k=Maxloading(w,c1,c2,n,bestx);

if(k!=-1)cout<<\总体最优装载：\ return 1; }

五、结果运行与分析：

贪心算法：

回溯法：

六、心得与体会：

通过本次实验，自己再次的联系了贪心算法和回溯法的应用，本次实验自己测试了很多次才成功，收获蛮大的，自己的编程能力进一步的提高了。

本文来源：https://www.bwwdw.com/article/nzff.html