OJ：http://acm.hdu.edu.cn/showproblem.php?pid=1059
大意：有6种不同大小的弹珠，价值依次为1-6。现在给你一些这些不同种类的弹珠，让你进行分配，使两个人手上的弹珠价值之和相同，一个弹珠不能划分。
01背包问题，就是种物品只有一个，多重背包问题，就是每种物品有指定个，完全背包问题，就是每种物品有无穷个。
这个题看起来像一个多重背包问题，每一种类型的弹珠为有限个，要求能组合成指定的数目。
所有弹珠加在一起有一个总和sum，如果和为奇数，就说明肯定不能平均分
如果和为偶数，就尝试去平均分，因为和为偶数也不一定能平均分。
如何尝试去划分呢?这就需要使用到多重背包了，这里不讲解多重背包！
多重背包：https://blog.csdn.net/qq_38984851/article/details/81133840
现在的背包的总大小是等于我们所有物品的价值的总和，且物品的价值是等于物品所占空间的，那么如果说当背包容量使用了一半的时候，背包中物品的价值刚好也是价值总和的一半，说明了这些弹珠能被完全的分为两堆！
#include <stdio.h> #include <stdlib.h> #include <string.h> #define max(x,y) x > y ? x : y #define MAX 200000 int nums[7]; int dp[MAX]; int val[MAX]; int max; int main() { for(int t=1;1;t++){ max = 0; int k=0; for(int i=1;i<=6;i++){ scanf("%d",&nums[i]); max += i * nums[i]; for (int j = 1; j <= nums[i]; j <<=1){ // 将多重背包中的一种物品的多个划分01背包中的多种物品 val[k++] = j * i; nums[i] = nums[i] - j; } if (nums[i] > 0){ val[k++] = nums[i] * i; } } if(max == 0){ return 0; } if(max & 1){ printf("Collection #%d:\n",t); printf("Can't be divided.\n"); }else{ memset(dp,0,sizeof(dp)); max >>= 1; // 01背包 for (int i = 0; i < k; i++) { for (int j = max; j >=val[i]; j--) { dp[j] = max(dp[j], dp[j - val[i]] + val[i]); } } if(dp[max] == max){ printf("Collection #%d:\n",t); printf("Can be divided.\n"); }else{ printf("Collection #%d:\n",t); printf("Can't be divided.\n"); } } printf("\n"); } }
解法2：效率上高一点，没有将多重背包中的物品进行拆分，而是直接将其进行展开，使用01背包的思路进行递归就可以了
#include<stdlib.h> #include<stdio.h> #include<string.h> int nums[6]; int dfs(int sum,int num){ if(sum == 0){ return 1; } if(num < 1){ return 0; } // 如果当前num种类的弹珠已经没有了或者剩余的需要的value值小于当前num // num直接减小，就去使用下一个弹珠了 while(num > 0 && (nums[num-1] == 0 || sum < num)){ num--; } // 使用了一个当前种类的物品 // 第num个弹珠可以使用0-nums[num-1]次。 nums[num-1]--; return (dfs(sum - num,num) || dfs(sum,num-1)); } int main(){ for(int t=1;1;t++){ int sum = 0; for(int i=0;i<6;i++){ scanf("%d",&nums[i]); sum += (i+1) * nums[i]; } if(sum == 0){ return 0; } if(sum % 2){ printf("Collection #%d:\n",t); printf("Can't be divided.\n"); printf("\n"); continue; } // 将总价值除2 sum /= 2; // 使用这些弹珠去凑成sum if(!dfs(sum,6)){ printf("Collection #%d:\n",t); printf("Can't be divided.\n"); }else{ printf("Collection #%d:\n",t); printf("Can be divided.\n"); } printf("\n"); } return 0; }
