/*----------------------------------------------------- 给出n个物体，第i个物体的重量为wi。 选择尽量多的物体，使得总重量不超过C。 输入： n和C以及n个整数表示的wi。 输出： 按照输入物体的顺序输出n个用空格分隔的Y或N。 Y表示该物体被选中，N表示不被选中。 最后一行输出所选中的物体的个数num和总重量w,用空格分隔。
注意：这个地方每个物体是不可再分割的整体。 思路： 先把所有物体按重量排序（从小到大排序） ， 然后贪心选择重量比较小的物体直到所选物体的总重量超过所允许的最大重量C 。 -------------------------------------------------------*/
输入案例：
10 100
20
20
5
25
28
10
3
4
8
9
输出案例：
Y Y Y N N Y Y Y Y Y
79 8
1 #include<stdio.h> 2 #include<stdlib.h> 3 4 struct obj 5 { 6 int weight; 7 int id; 8 int flag;//标示该物体是否被选中。 0标示未被选中，1表示被选中。 9 }; 10 11 void merge_sort1(struct obj *A,int x,int y,struct obj *T);//采用归并排序对A数组排序。按struct obj的weight从小到大排序。 12 void merge_sort2(struct obj *A,int x,int y,struct obj *T);//采用归并排序对A数组排序。按struct obj的id从小到大排序。 13 14 int cmp1(struct obj a,struct obj b);//按struct obj的weight比较a和b的大小 15 int cmp2(struct obj a,struct obj b);//按struct obj的id比较a和b的大小 16 int cmpQsort1(const void *a,const void *b);//按struct obj的weight比较a和b的大小 17 int cmpQsort2(const void *a,const void *b);//按struct obj的id比较a和b的大小 18 19 int main() 20 { 21 int n,c,i,w,num; 22 struct obj *arr,*T; 23 freopen("5.in","r",stdin); 24 scanf("%d%d",&n,&c); 25 arr=(struct obj *)malloc(sizeof(struct obj)*n); 26 T=(struct obj *)malloc(sizeof(struct obj)*n); 27 for(i=0;i<n;i++) 28 { 29 scanf("%d",&arr[i].weight); 30 arr[i].id=i+1; 31 arr[i].flag=0; 32 } 33 qsort(arr,n,sizeof(struct obj),cmpQsort1); 34 //merge_sort1(arr,0,n,T);//按重量排序 35 /*for(i=0;i<n;i++) printf("%-3d %-3d\n",arr[i].weight,arr[i].id); 36 printf("\n"); 37 merge_sort2(arr,0,n,T);//按id排序 38 for(i=0;i<n;i++) printf("%-3d %-3d\n",arr[i].weight,arr[i].id);*/ 39 40 w=0;//所选物体的总重量 41 num=0;//所选物体的个数 42 for(i=0;i<n;i++) 43 { 44 w=w+arr[i].weight;//选中arr[i] 45 arr[i].flag=1; 46 num++;//选中的个数加1 47 if(w>c) 48 { 49 w-=arr[i].weight; 50 arr[i].flag=0; 51 num--; 52 break; 53 } 54 } 55 qsort(arr,n,sizeof(struct obj),cmpQsort2); 56 //merge_sort2(arr,0,n,T);//按id排序 57 for(i=0;i<n;i++)//其实被选中的个数和总重量可以在这个for里面统计。但是总重量不管如何在前面贪心选择的过程中都该要记录的。 58 { 59 if(arr[i].flag==1) printf("Y "); 60 else printf("N "); 61 } 62 printf("\n%d %d\n",w,num); 63 64 free(arr); 65 free(T); 66 return 0; 67 } 68 void merge_sort1(struct obj *A,int x,int y,struct obj *T) 69 {//采用归并排序对A数组排序。按struct obj的weight从小到大排序。 70 if(y-x>1) 71 { 72 int m=x+(y-x)/2; //划分 73 int p=x,q=m,i=x; 74 merge_sort1(A,x,m,T); 75 merge_sort1(A,m,y,T); 76 while(p<m||q<y) 77 { 78 //if(q>=y||(p<m&&A[p]<=A[q])) T[i++]=A[p++]; 79 if(q>=y||(p<m&&A[p].weight<=A[q].weight)) T[i++]=A[p++]; 80 //if(q>=y||(p<m&&cmp1(A[p],A[q])==-1)) T[i++]=A[p++]; 81 else T[i++]=A[q++]; 82 } 83 for(i=x;i<y;i++) A[i]=T[i]; 84 } 85 } 86 void merge_sort2(struct obj *A,int x,int y,struct obj *T) 87 {//采用归并排序对A数组排序。按struct obj的id从小到大排序。 88 if(y-x>1) 89 { 90 int m=x+(y-x)/2; //划分 91 int p=x,q=m,i=x; 92 merge_sort2(A,x,m,T); 93 merge_sort2(A,m,y,T); 94 while(p<m||q<y) 95 { 96 //if(q>=y||(p<m&&A[p]<=A[q])) T[i++]=A[p++]; 97 if(q>=y||(p<m&& A[p].id<=A[q].id)) T[i++]=A[p++]; 98 //if(q>=y||(p<m&&cmp2(A[p],A[q])==-1)) T[i++]=A[p++]; 99 else T[i++]=A[q++]; 100 } 101 for(i=x;i<y;i++) A[i]=T[i]; 102 } 103 } 104 int cmp1(struct obj a,struct obj b) 105 {//按struct obj的weight比较a和b的大小 106 if(a.weight>b.weight) return 1; 107 else if(a.weight<b.weight) return -1; 108 else return 0; 109 } 110 int cmp2(struct obj a,struct obj b) 111 {//按struct obj的id比较a和b的大小 112 if(a.id>b.id) return 1; 113 else if(a.id<b.id) return -1; 114 else return 0; 115 } 116 int cmpQsort1(const void *a,const void *b) 117 {//按struct obj的weight比较a和b的大小 118 int t=((struct obj *)a)->weight-((struct obj *)b)->weight; 119 if(t>0) return 1; 120 else if(t<0) return -1; 121 else return 0; 122 } 123 int cmpQsort2(const void *a,const void *b) 124 {//按struct obj的id比较a和b的大小 125 int t=((struct obj *)a)->id-((struct obj *)b)->id; 126 if(t>0) return 1; 127 else if(t<0) return -1; 128 else return 0; 129 }
