最优装载（贪心）

题目描述

有一批集装箱要装上一艘载重量为C的轮船。其中集装箱i的重量为wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船

输入

第一行是一个整数n（ n <= 1000 ）和一个非负数C（ C <= 10000 ），分别表示集装箱的个数以及轮船的载重量。接下来有n行，每行一个非负数，表示每个集装箱的编号和重量。

输出

输出集装箱的个数以及这时的总重量以及相应的编号

样例输入

5 100 1 20 2 50 3 120 4 99 5 30

样例输出

3 100 1 5 2

和背包的思想类似，要想集装箱尽可能的多，那么就从小到大开始装起，怎么装：就一个一个的去装看剩余的空间能否装下就行~ #include<stdio.h> #include<algorithm> using namespace std; struct Node{ int order,weight; }str[1005]; bool cmp(Node x,Node y){ if(x.weight==y.weight){ return x.order<y.order; } else{ return x.weight<y.weight; } } int main(){ int n,c,num=0; scanf("%d %d",&n,&c); for(int i=0;i<n;i++){ scanf("%d %d",&str[i].order,&str[i].weight); } sort(str,str+n,cmp); int a[1005],sum=0; for(int i=0;i<n;i++){ if(str[i].weight<=c){ num++; c-=str[i].weight; sum+=str[i].weight;//用来计算总重量 a[i]=str[i].order;//用来存编号 } else{ break; } } printf("%d\n%d\n",num,sum); for(int i=0;a[i]!='\0';i++){//'\0' printf("%d ",a[i]); } return 0; }