天之道

享受编程的乐趣。
posts - 118, comments - 7, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

贪心算法之最优装船问题

Posted on 2012-03-12 14:10 hoshelly 阅读(655) 评论(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<&& 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;
}




只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理