Posted on 2012-03-12 14:10
hoshelly 阅读(638)
评论(0) 编辑 收藏 引用 所属分类:
C
题目：
有一批集装箱要装入一个载质量为C的货船中，每个集装箱的质量由用户自己输入指定，在货船的装载体积不限的前提下，如何装载集装箱才能尽可能多地的将集装箱装入货船中。
每次选取质量最小的箱子装入船（用冒泡排序算法解决），代码如下：
#include<stdio.h>
#include<stdlib.h>
void sort(int w[],int t[],int n)//w[]存放每个集装箱的质量，t[]存放w[]的下标
{
int i,j,tmp;
int *w_tmp=(int *)malloc(sizeof(int)*n);//开辟一个临时数组，存放w[]的内容，用于排序
for(i=0;i<n;i++)
t[i]=i;//初始化数组t
for(i=0;i<n;i++)
w_tmp[i]=w[i];
for(i=0;i<n-1;i++)
for(j=0;j<n-i-1;j++)//冒泡排序实现
if(w_tmp[j]>w_tmp[j+1])
{
tmp=w_tmp[j];
w_tmp[j]=w_tmp[j+1];
w_tmp[j+1]=tmp;
tmp=t[j];
t[j]=t[j+1];
t[j+1]=tmp;
}
}
void loading(int x[],int w[],int c,int n)
{
int i,s=0;
int *t=(int*)malloc(sizeof(int)*n);//动态开辟一个临时数组，存放w[]的下标
sort(w,t,n);
for(i=0;i<n;i++)
x[i]=0;
for(i=0;i<n && w[t[i]]<=c;i++){
x[t[i]]=1; //将第t[i]个集装箱装入货船中
c=c-w[t[i]]; //变量c中存放货船的剩余载质量
}
}
int main()
{
int x[5],w[5],c,i;
printf("Iput the maximum loading of the sheep\n");
scanf("%d",&c);
printf("Iput the weight of Five box\n");
for(i=0;i<5;i++)
scanf("%d",&w[i]);
loading(x,w,c,5);
printf("The following boxes will be loaded\n");
for(i=0;i<5;i++)
{
if(x[i]==1) printf("BOX:%d ",i);
}
return 0;
}