/*-----------------------------------------------------
有n个物体，第i个物体的重量是wi，价值为vi，
选若干个物体，使得在总重量不超过c的情况下让总价值尽量高。
这里每个物体都可以只取走一部分，价值和重量按比例计算。
输入：
第一行输入两个整数表示n和c。
第2到第n+1行每行两个整数分别表示wi和vi。
输出：
第一行输出所选物品的总价值v和总重量w以及所选物品的种类数num。两两之间用空格分隔。
第二行到第n+1行按照输入物品的顺序输出每种物品被选择的重量。（不被选择的输出0）
思路：
这个题目应该综合考虑重量和价值两个因素，所以要计算出每一种物体
单位重量的价值price，然后按照price从大到小排序。
贪心选择的策略：优先选择price比较大的那种物体。
除了最后一个物体之外，每种物体要么全部选，要么全部不选。
最后一个被选中的物体可能限于总重量C的大小，只能选一部分。
-------------------------------------------------------*/
1 #include<stdio.h>
2 #include<stdlib.h>
3 struct obj
4 {
5 int weight;
6 int value;
7 int id;
8 double price;//表示该物体单位重量的价值。
9 int select;//表示该物体被选中的数量
10 };
11
12 void merge_sort1(struct obj *A,int x,int y,struct obj *T);//采用归并排序对A数组排序。按struct obj的price从大到小排序。
13 void merge_sort2(struct obj *A,int x,int y,struct obj *T);//采用归并排序对A数组排序。按struct obj的id从小到大排序。
14
15 int cmp1(struct obj a,struct obj b);//按struct obj的price比较a和b的大小
16 int cmp2(struct obj a,struct obj b);//按struct obj的id比较a和b的大小
17 int cmpQsort1(const void *a,const void *b);//按struct obj的price比较a和b的大小
18 int cmpQsort2(const void *a,const void *b);//按struct obj的id比较a和b的大小
19
20 int main()
21 {
22 int n,c,i;
23 long w,num;
24 double v;
25 int t;
26 struct obj *a,*temp;
27 freopen("5.in","r",stdin);
28 scanf("%d %d",&n,&c);
29 a=(struct obj*)malloc(sizeof(struct obj)*n);
30 temp=(struct obj*)malloc(sizeof(struct obj)*n);
31 for(i=0;i<n;i++)
32 {
33 scanf("%d%d",&a[i].weight,&a[i].value);
34 a[i].id=i+1;
35 a[i].price=a[i].value*1.0/a[i].weight;
36 a[i].select=0;
37 }
38 qsort(a,n,sizeof(struct obj),cmpQsort1);
39 //merge_sort1(a,0,n,temp);//按单位重量的价值price排序
40 /*for(i=0;i<n;i++) printf("%-3d %-3d %-3d %-10.3lf\n",a[i].value,a[i].weight,a[i].id,a[i].price);
41 printf("\n");
42 merge_sort2(a,0,n,temp);//按id排序
43 for(i=0;i<n;i++) printf("%-3d %-3d %-3d %-10.3lf\n",a[i].value,a[i].weight,a[i].id,a[i].price);*/
44
45 v=0; //所选择的物体总价值
46 w=0; //所选择的物体总重量
47 num=0; //所选择的物体个数
48 for(i=0;i<n;i++)
49 {
50 w=w+a[i].weight;
51 v=v+a[i].value;
52 a[i].select=a[i].weight;
53 num++;
54 if(w>=c)
55 {
56 if(w==c)
57 {
58 break;
59 }
60 else
61 {
62 t=w-c;
63 v=v-a[i].value*1.0/a[i].weight*t;
64 w=c;
65 a[i].select=a[i].select-t;
66 break;
67 }
68 }
69 }
70 qsort(a,n,sizeof(struct obj),cmpQsort2);
71 //merge_sort2(a,0,n,temp);//按id排序
72 printf("%.2lf %ld %ld\n",v,w,num);
73 for(i=0;i<n;i++)
74 {
75 printf("%d\n",a[i].select);
76 //printf("%-3d %-3d %-3d %-10.3lf %d\n",a[i].value,a[i].weight,a[i].id,a[i].price,a[i].select);
77 }
78
79 free(a);
80 free(temp);
81 return 0;
82 }
83
84 void merge_sort1(struct obj *A,int x,int y,struct obj *T)
85 {//采用归并排序对A数组排序。按struct obj的weight从大到小排序。
86 if(y-x>1)
87 {
88 int m=x+(y-x)/2; //划分
89 int p=x,q=m,i=x;
90 merge_sort1(A,x,m,T);
91 merge_sort1(A,m,y,T);
92 while(p<m||q<y)
93 {
94 //if(q>=y||(p<m&&A[p]<=A[q])) T[i++]=A[p++];
95 if(q>=y||(p<m&&A[p].price>=A[q].price)) T[i++]=A[p++];
96 //if(q>=y||(p<m&&cmp1(A[p],A[q])==1)) T[i++]=A[p++];
97 else T[i++]=A[q++];
98 }
99 for(i=x;i<y;i++) A[i]=T[i];
100 }
101 }
102 void merge_sort2(struct obj *A,int x,int y,struct obj *T)
103 {//采用归并排序对A数组排序。按struct obj的id从小到大排序。
104 if(y-x>1)
105 {
106 int m=x+(y-x)/2; //划分
107 int p=x,q=m,i=x;
108 merge_sort2(A,x,m,T);
109 merge_sort2(A,m,y,T);
110 while(p<m||q<y)
111 {
112 //if(q>=y||(p<m&&A[p]<=A[q])) T[i++]=A[p++];
113 if(q>=y||(p<m&& A[p].id<=A[q].id)) T[i++]=A[p++];
114 //if(q>=y||(p<m&&cmp2(A[p],A[q])==-1)) T[i++]=A[p++];
115 else T[i++]=A[q++];
116 }
117 for(i=x;i<y;i++) A[i]=T[i];
118 }
119 }
120 int cmp1(struct obj a,struct obj b)
121 {//按struct obj的price比较a和b的大小
122 if(a.price>b.price) return 1;
123 else if(a.price<b.price) return -1;
124 else return 0;
125 }
126 int cmp2(struct obj a,struct obj b)
127 {//按struct obj的id比较a和b的大小
128 if(a.id>b.id) return 1;
129 else if(a.id<b.id) return -1;
130 else return 0;
131 }
132 int cmpQsort1(const void *a,const void *b)
133 {//按struct obj的price比较a和b的大小
134 int t=((struct obj *)b)->price-((struct obj *)a)->price;
135 if(t>0) return 1;
136 else if(t<0) return -1;
137 else return 0;
138 }
139 int cmpQsort2(const void *a,const void *b)
140 {//按struct obj的id比较a和b的大小
141 int t=((struct obj *)a)->id-((struct obj *)b)->id;
142 if(t>0) return 1;
143 else if(t<0) return -1;
144 else return 0;
145 }
运行案例：
输入：
10 100
20 50
20 30
5 200
25 250
28 28
10 200
3 300
4 200
8 16
9 90
输出：
1330.00 100 9
20
16
5
25
0
10
3
4
8
9