首页 > 代码库 > 杭电1059
杭电1059
1 //简单的背包应用,奈何我摔了好几次 2 #include<stdio.h> 3 #include<string.h> 4 #define maxn 120000 5 int n[6]; 6 int a[maxn]; 7 int Room; 8 void zero_one_bag(int); 9 void complete_bag(int); 10 void multiple_bag(int,int); 11 int main() 12 { 13 int ant=0; 14 while(~scanf("%d%d%d%d%d%d",&n[0],&n[1],&n[2],&n[3],&n[4],&n[5]) && n[0]+n[1]+n[2]+n[3]+n[4]+n[5]) 15 { 16 printf("Collection #%d:\n",++ant); 17 Room=n[0]*1+n[1]*2+n[2]*3+n[3]*4+n[4]*5+n[5]*6; 18 if(Room%2) 19 puts("Can‘t be divided.\n"); 20 else 21 { 22 memset(a,0,sizeof a); 23 a[0]=1; 24 Room/=2; 25 for(int i=0; i<6; ++i) 26 if(n[i]) 27 multiple_bag(i+1,n[i]); 28 if(a[Room]) 29 puts("Can be divided.\n"); 30 else 31 puts("Can‘t be divided.\n"); 32 } 33 } 34 } 35 36 void zero_one_bag(int room) 37 { 38 for(int i=Room; i>=room; --i) 39 { 40 if(a[i-room]) 41 a[i]=1; 42 } 43 } 44 45 void complete_bag(int room) 46 { 47 for(int i=room; i<=Room; ++i) 48 { 49 if(a[i-room]) 50 a[i]=1; 51 } 52 } 53 54 void multiple_bag(int room,int num) 55 { 56 if(room * num >= Room) 57 { 58 complete_bag(room); 59 return ; 60 } 61 62 for(int k=1; k<num; k*=2) 63 { 64 zero_one_bag(room*k); 65 num-=k; 66 } 67 zero_one_bag(room*num); 68 }
杭电1059
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。