貪心法――乘船問(wèn)題
來(lái)源：程序員人生 發(fā)布時(shí)間：2015-03-11 08:39:49 閱讀次數(shù)：4509次
題目大致是：
有n個(gè)人，第i個(gè)人的重量為w[i]，每艘船的最大載重量均為c，且最多只能乘兩個(gè)人。用最少的船裝載所有人。
解：
首先從最輕的人開始斟酌，那末他應(yīng)當(dāng)和最重的人去坐，如果每一個(gè)人都不能和它坐船，那末唯1的方法就是每一個(gè)人做1艘船。
否則，他應(yīng)當(dāng)選擇能夠和他1起坐船的人中最重的那個(gè)，這模樣才不會(huì)浪費(fèi)。
#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:如果它們兩個(gè)的重量和小于等于c的話，并且j這個(gè)人沒有被其他人給拉去，那末這是1種；
if(a[i].w+a[j].w<=c && book[j]==0){
num++; book[i]=1; book[j]=1; break;
}
//two:如果它們兩個(gè)的重量和大于c的話且j這個(gè)人沒有被拉去，那末j那個(gè)人只能自己和自己1個(gè)人坐1條船了；
else if(a[i].w+a[j].w>c && book[j]==0){
num++; book[j]=1;
}
}
//如果上面的都循環(huán)完了，但是i還是沒有滿足的條件，那末說(shuō)明它也只能自己坐1條船了；
if(!book[i]) {num++; book[i]=1;}
}
printf("%d
",num);
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
