最优装载问题
湖南涉外经济学院 计算机科学与技术专业
《算法设计与分析》课程
实 验 报 告
班级： 学号： 姓名： 教师：
成绩：
2012年6月
【实验目的】
1 掌握最优装载的相关算法 2 利用贪心算法实现最优装载问题
3 分析实验结果，总结算法的时间和空间复杂度。思考是否能将算法的时间复杂度提高到O(nlgn) 【系统环境】 Windows XP 平台 【实验工具】 VC++6.0英文企业版 【问题描述】
描述： 有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载 问题要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 问题可形式化描述为：
Max (x1+x2+…+xn) W1*x1+….+Wn*xn
从剩下的集装箱中，选择重量最小的集装箱。这种选择次序可以保证所选的集装箱总重量最小，从而可以装载更多的集装箱。根据这种贪心策略，首先选择最轻的集装箱，然后选择次轻的，如此下去直到所有集装箱均装上船或穿上不能容纳其他任何一个集装箱。 假设n=8,[W1,W2,…,W8]=[100,200,50,90,150,50,20,80],c=400。利用贪心算法时，所考察集装箱的顺序为7,3,6,8,4,1,5,2。集装箱7,3,6,8,4,1的总重量为390个单位且已被装载，剩下的装载能力为10个单位，小于剩下的任何一个集装箱。在这种贪心解决算法中得到[x1,x2,…x8]=[1,0,1,1,0,1,1,1]，且∑xi=6。 【源程序代码】
#include #include #include #include
using namespace std; #define N 100
int tx[N],tx1[N]; /*
排序函数 */
void Sort(int *w,int *t,int &n) {
int i,j,m;
int *w1=new int[n+1]; int tem;
for(i=1;i
cout
for(i=1;iw[j])
{ tem=w[j]; w[j]=w[i]; w[i]=tem; }
cout
cout
for(i=1,j=1;i
if(w[i]==w1[j]) {
m=j; if(m
for(;m
if(w[i]==w1[m]) { t[i]=m;
printf("%d--",t[i]); i++; j=0; } } else {
t[i]=j;
printf("%d--",t[i]); i++; j=0;
}
} }
void Loading(int *w,int *t,int &c,int &n,int &m) {
int i,j;
int weight=0,min; Sort(w,t,n);
for(i=1;i
min=weight+w[i]; if(min
weight+=w[i];
tx[i]=1; //装入一个集装箱，就把该集装箱标号置一并记录下来 } }
m=i-1; //记录装入的集装箱的个数。 }
void main() {
int t[N],w0[N],w[N],a[N],n,c,m,i,j,r;
int max,temp; //记录装入的集装箱的最大重量。 max=0;
cout>c;
cout>n;
cout
//cin>>w0[i]; //w[i+1]=w0[i];
w0[i]=rand()%100+1; //通过随机函数得到各集装箱的重量 w[i+1]=w0[i]; cout
}
Loading(w,t,c,n,m); //m记录装入的集装箱实际数量 ；t记录集装箱重量从小到大的下标值
cout
}
for(i=1,r=0;i
if(tx[i]) {
max+=w[i];
a[r]=w[i]; //把装入轮船的集装箱记录入数组a r++;
cout
cout
for(i=0;i
if(w0[i]==a[j]) { tx1[i]=1; }
}
cout
cout
cout
}
【实验结果】
1. 下面的是有相同重量的集装箱，可见标号没有相同的。
2. 下面是没有相同重量的集装箱的测试结果。