题目描述
给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。
已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，
编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。
输入
第一行输入两个整数M和N，用空格隔开
第二行到第N+1行每一行输入两个数wi和vi，表示第i种物品的重量和单位价值。
输出
使得装货价值最大的装货方案和总价值。
先输出若干行，每一行输出货物编号和该种货物装货的重量。
最后一行输出该种装货方案所装物品的总价值。
【算法分析】
贪心算法策略：因为每一个物品都可以分割成单位块，
单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，
可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，
然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。
1 #include<stdio.h> 2 #include<stdlib.h> 3 struct obj 4 { 5 int id; 6 double w; 7 double v; 8 }; 9 int cmp(const void *a,const void *b) 10 { 11 double ans= ((struct obj*)b)->v -((struct obj*)a)->v; 12 if(ans<0) return -1; 13 else if(ans>0) return 1; 14 else return 0; 15 } 16 int main() 17 { 18 double M; 19 int N; 20 struct obj *a; 21 int i; 22 double maxV=0; 23 24 scanf("%lf%d",&M,&N); 25 26 if(M<=0) 27 { 28 printf("输入的数据可能不正确：汽车空间不能为0或负数。\n"); 29 return 0; 30 } 31 32 a=(struct obj *)malloc(N*sizeof(struct obj)); 33 for(i=0;i<N;i++) 34 { 35 a[i].id=i+1; 36 scanf("%lf%lf",&a[i].w,&a[i].v); 37 } 38 39 qsort(a,N,sizeof(struct obj),cmp); 40 41 for(i=0;i<N&&M>0;i++) 42 { 43 if(a[i].w<=M) 44 { 45 printf("%d %lf\n",a[i].id,a[i].w); 46 M=M-a[i].w; 47 maxV=maxV+a[i].v*a[i].w; 48 } 49 else 50 { 51 printf("%d %lf\n",a[i].id,M); 52 maxV=maxV+M*a[i].v; 53 M=0; 54 break; 55 } 56 } 57 printf("%lf\n",maxV); 58 free(a); 59 return 0; 60 }
