Posted on 2012-03-12 14:10
hoshelly 閱讀(690)
評論(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;
}