国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > 贪心法――乘船问题

贪心法――乘船问题

来源:程序员人生   发布时间:2015-03-11 08:39:49 阅读次数:4344次

题目大致是:
有n个人,第i个人的重量为w[i],每艘船的最大载重量均为c,且最多只能乘两个人。用最少的船装载所有人。

解:
首先从最轻的人开始斟酌,那末他应当和最重的人去坐,如果每一个人都不能和它坐船,那末唯1的方法就是每一个人做1艘船。
否则,他应当选择能够和他1起坐船的人中最重的那个,这模样才不会浪费。

 

#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; struct node{ int w; }a[1001]; bool cmp(node a,node b){ return a.w<b.w; } int main(){ int i,j,n,c; int book[1001]={0}; scanf("%d%d",&n,&c); for(i=1;i<=n;i++) scanf("%d",&a[i].w); sort(a+1,a+1+n,cmp); int num=0; for(i=1;i<=n;i++){ //book[i]=1; for(j=n;j>=1;j--){ //one:如果它们两个的重量和小于等于c的话,并且j这个人没有被其他人给拉去,那末这是1种; if(a[i].w+a[j].w<=c && book[j]==0){ num++; book[i]=1; book[j]=1; break; } //two:如果它们两个的重量和大于c的话且j这个人没有被拉去,那末j那个人只能自己和自己1个人坐1条船了; else if(a[i].w+a[j].w>c && book[j]==0){ num++; book[j]=1; } } //如果上面的都循环完了,但是i还是没有满足的条件,那末说明它也只能自己坐1条船了; if(!book[i]) {num++; book[i]=1;} } printf("%d ",num); }


 

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生