大理石分割问题

心已赠人 2022-11-19 09:48 131阅读 0赞

## 大理石分割问题 ##

有若干块大理石，其大小及美观程度不一，为了比较客观的分割这些大理石，我们需要先给这些大理石一个评分，评分分为6个等级，分别用1~6的数字来表示。现希望将这些大理石分成两部分，使每部分的评分之和相同。  
输入：  
输入一行，包括6个数，分别是每个等级的大理石的数量。每种等级的大理石数量不超过20000.  
输出：  
如果这些大理石能否分割成评价等级之和相同的两部分，则输出true，否则输出false.

样例输入：
        1 0 1 2 0 0
    样例输出：
        false

方法一：采用二进制的解法，看的其他人写的，没有太懂原理，想要了解的话可以去看看多重背包的二进制解法：

/*poj1014 AC*/
    #include<cstdio>
     
    long sum,v,tot,i,j;
    bool f[100000];
    long num[7];
     
     
    void Zeroonepack(int weight)
    { 
         for (long j=v;j>=weight;j--)
           if (f[j-weight]) 
    		   f[j]=true;
    }
           
     
     
    void Multiplepack(int num,int weight)
    { 
         long k=1;
         if(num==1) {  
    		 Zeroonepack(weight); 
    		 return;
    	 }
         while(k<num)
         { 
            Zeroonepack(k*weight); //拆分
            num-=k;
            k*=2;
         }
         if(num) 
    		 Zeroonepack((num)*weight); //NUM!
    } 
                
     
    int main()
    { 
        while (1) { 
    	   tot++;
           bool b=false;
           sum=0;
           for (i=1;i<=6;i++) 
           { 
              scanf("%ld",&num[i]);
              if(num[i]) b=true;
    	      sum+=i*num[i];
           }
           if (!b) break; //都为0，break
           if (sum%2){ 
                printf("Collection #%ld:\nCan't be divided.\n\n",tot);
                continue;
           }
           v=sum/2; //划分为两部分
           for(i=1;i<=v;i++) 
    		   f[i]=false;
           f[0]=true;
           for (i=1;i<=6;i++){ 
             Multiplepack(num[i],i);
    		 for(j=1;j<=v;j++){  
    			 int a=f[j];
    			 printf("%d\t",f[j]);
    		 }
    		 printf("\n");
    	   }
           if(f[v]){ 
    		   int b=1;
    		   printf("Collection #%ld:\nCan be divided.\n\n",tot);
    	   }
           else{ 
    		   int b=0;
    		   printf("Collection #%ld:\nCan't be divided.\n\n",tot);
           }
    	   }
    }

方法二：比较简单的递归回溯方法，对于解空间树与搜索空间树都能够很好地画出来，也能很快理解原理，代码如下：（如转载需标明出处）

#include<stdio.h>
    
    int counts[7];
    int flag = 0;
    void solve(int half,int fetch) { 
    	if (half == fetch) { 
    		flag = 1;
    		return;
    	}
    	if (fetch < half) { 
    		for (int i = 1; i <= 6; i++) { 
    			if (counts[i]) { 
    				counts[i]--;
    				fetch += i;
    				if (fetch > half) { 
    					counts[i]++;
    					fetch -= i;
    					continue;
    				}
    				solve(half, fetch);
    			}
    		}
    	}
    
    }
    
    int main() { 
    	int tCase = 1;
    	while (1) { 
    		int sum = 0;
    		for (int i = 1; i <= 6; i++) { 
    			scanf("%d",&counts[i]);
    			sum += counts[i]*i;
    		}
    		printf("Collection # %d:\n",tCase++);
    		if (sum % 2){ 
    			printf("Can't be divided.\n\n");
    			continue;
    		}
    		flag = 0;
    		solve(sum / 2, 0);
    		if (flag) { 
    			printf("Can be divided.\n\n");
    		} else { 
    			printf("Can't be divided.\n\n");
    		}
    	}
    	return 0;
    }

运行截图如下：  
![在这里插入图片描述][20210121150017472.png]

[20210121150017472.png]: /images/20221119/d25f3e121e564ee993979508e2d66ba8.png