首页 > 代码库 > 贪心算法练习题：部分背包问题
贪心算法练习题：部分背包问题
/*-----------------------------------------------------有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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。