InputEach line in the input describes one collection of marbles to be divided. The lines consist of six non-negative integers n1, n2, ..., n6, where ni is the number of marbles of value i. So, the example from above would be described by the input-line ``1 0 1 2 0 0‘‘. The maximum total number of marbles will be 20000.
The last line of the input file will be ``0 0 0 0 0 0‘‘; do not process this line.
OutputFor each colletcion, output ``Collection #k:‘‘, where k is the number of the test case, and then either ``Can be divided.‘‘ or ``Can‘t be divided.‘‘.
Output a blank line after each test case.
Sample Input
1 0 1 2 0 0 1 0 0 0 1 1 0 0 0 0 0 0
Sample Output
Collection #1: Can‘t be divided. Collection #2: Can be divided
题目大意：
有六种弹珠，价值分别是1、2、3、4、5、6，给定每种弹珠的数量，问能否分成价值相等的两份。
#include<stdio.h> #include<string.h> #define N 100010 int dp[N],Vect; int max(int a,int b){return a>b?a:b;} void zeroonepack(int use,int weight)//（01背包） { for(int v=Vect;v>=use;v--)//递减开始，为了防止背包里重复放当前同一物品 dp[v]=max(dp[v],dp[v-use]+weight); } void complexepack(int use,int weight)//完全背包 { for(int v=use;v<=Vect;v++)//递增开始，背包中可以放多个当前同一物品 dp[v]=max(dp[v],dp[v-use]+weight); } void miltpack(int use,int weight,int n)//n为当前物品的数量（多重背包） { if(n*use>=Vect)//当超出背包空间时，变成完全背包 complexepack(use,weight); else//当没有超出，则为01背包 { int k=1; while(k<n)//把当前物品分成多种类型 { zeroonepack(k*use,k*weight); n-=k; k*=2; } zeroonepack(n*use,n*weight);//剩下作为一种 } } int main() { int nn[8],c=0; while(1) { Vect=0; for(int i=1;i<=6;i++) { scanf("%d",&nn[i]); Vect+=nn[i]*i; } if(Vect==0)break; if(Vect%2!=0) printf("Collection #%d:\nCan‘t be divided.\n\n",++c); else { Vect/=2; for(int i=0;i<=Vect;i++) dp[i]=0; for(int i=1;i<=6;i++) if(nn[i]) miltpack(i,i,nn[i]); if(dp[Vect]==Vect) printf("Collection #%d:\nCan be divided.\n\n",++c); else printf("Collection #%d:\nCan‘t be divided.\n\n",++c); } } }
原文：https://www.cnblogs.com/lipu123/p/12189924.html