2015-06-07
问题简述：
有六样物品，其值分别为1,2,3,4,5,6，现在有一部分这些物品，需要把这些物品分为两部分，输出是否能让这两部分的值总和相等。
原题链接：http://poj.org/problem?id=1014
解题思路：
显然可以将所有物品值的总和加起来，以总和的一半为一个背包的限额，可以将这个问题转化为多重背包问题。但是这里我要使用另外一种方法----DFS。
DFS：从最大值为6开始向下深搜，由于值为6的物品可能有很多个，所以下一个搜索仍然从6开始（当值为6的物品用完时，继续向下搜索）。
源代码：
1 /* 2 OJ: POJ 3 ID: 3013216109 4 TASK: 1014.Dividing 5 LANG: C++ 6 NOTE: DFS 7 */ 8 #include <cstdio> 9 10 int n[6],k=1,sum; 11 12 bool dfs(int x) { 13 if(x==sum/2) return true; //如果正好搜索到总和的一半，则成功 14 for(int i=5;i>=0;i--) { 15 if(n[i]&&x+i+1<=sum/2) { 16 n[i]--; 17 if(dfs(x+i+1)) 18 return true; 19 } 20 } 21 return false; 22 } 23 24 int main() 25 { 26 while(scanf("%d",&n[0])!=EOF) { 27 sum=n[0]; 28 for(int i=1;i<6;i++) { 29 scanf("%d",&n[i]); 30 sum+=(n[i]*(i+1)); 31 } 32 if(sum==0) break; 33 printf("Collection #%d:\n",k++); 34 if(sum%2==1) { 35 printf("Can‘t be divided.\n\n"); 36 continue; 37 } 38 if(dfs(0)) 39 printf("Can be divided.\n\n"); 40 else 41 printf("Can‘t be divided.\n\n"); 42 } 43 return 0; 44 }
原文：http://www.cnblogs.com/ACMans/p/4559599.html