1 /*
2 Author: Leo.W
3 Descriptipn: 几个价值不一的大理石,是否能够两个人价值均分
4 How to Do: 先求的价值均分时的理论值ave_value,判断奇偶;若为偶数则转为完全背包问题求解,由于数量较大,可以模10以减小问题
5 规模,再DP求解,关键的是初始化dp[0]=0及dp数组初始为int类型的最小值。当得到dp[sum]>0,即存在一组可行解满足dp[0]开始取到sum。
6 */
7 #include <stdio.h>
8 #include <string.h>
9 #define MAXSIZE 120002
10 #define inf 0x7fffffff
11 #define max(x,y) x>y?x:y
12 int dp[MAXSIZE];
13 int value[6];
14 int main(){
15 //freopen("in.txt","r",stdin);
16 int i,j,k,no=1;
17 while(scanf("%d",&value[0])){
18 scanf("%d%d%d%d%d",&value[1],&value[2],&value[3],&value[4],&value[5]);
19 if(value[0]+value[1]+value[2]+value[3]+value[4]+value[5]==0)
20 break;
21 printf("Collection #%d:\n",no++);
22 int sum=0;
23 for(i=0;i<6;i++){
24 value[i]%=10;
25 sum+=value[i]*(i+1);
26 }
27 if(sum&1){
28 printf("Can't be divided.\n\n"); continue;
29 }
30 sum/=2;
31 for(i=0;i<MAXSIZE;i++) dp[i]=-inf-1;
32 dp[0]=0;
33 for(i=1;i<=6;i++){
34 for(j=1;j<=value[i-1];j++){
35 for(k=sum;k>=i;k--){
36 dp[k]=max(dp[k],dp[k-i]+1);
37 }
38 }
39 }
40 if(dp[sum]>0) printf("Can be divided.\n\n");
41 else printf("Can't be divided.\n\n");
42
43 }
44 return 0;
45 }
posted on 2012-03-07 15:03
Leo.W 阅读(490)
评论(3) 编辑 收藏 引用