/*多重背包.问题：N种物品和体积V的背包，第i件物品的体积是v[i],价值是w[i],每种n[i]件.求解：哪些物品放入背包里可以使物品价值最大.特点：每种物品有固定的件数,可以放0件,1件,2件,....n[i]件.状态转移方程：dp[i][j]=max(dp[i-1][j-k*v[i]]|0<=k<=n[i]);二进制优化：将第i种物品分成若干件物品,其中每件物品有一个系数,这件物品的价值和体积均是原来的物品的价值和体积乘以这个系数.1,2,4,.....n[i]-2^k.such as:13可以分成1,2,4,6四件物品.
*///NYoj 546 Divideing Jewels.
#include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b
int main()
{int a[15],k=0;while(~scanf("%d%d%d%d%d%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6],&a[7],&a[8],&a[9],&a[10])){int sum=0,v[105],w[105],dp[100005],top=0;sizeof(dp,0,sizeof(dp));for(int i=1;i<=10;i++)sum+=a[i]*i;if(!sum) break;for(int i=1;i<=10;i++)//二进制优化....{for(int k=1;k<=a[i];k=k*2){v[++top]=k*i;w[top]=k*i;a[i]-=k;}if(a[i]!=0){v[++top]=a[i]*i;w[top]=a[i]*i;a[i]=0;}}for(int i=1;i<=top;i++){for(int j=sum/2;j>=v[i];j--)dp[j]=max(dp[j],dp[j-v[i]]+w[i]);}if(dp[sum/2]*2==sum) printf("#%d:Can be divided.\n\n",++k);else printf("#%d:Can't be divided.\n\n",++k);}
}//TLE
#include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b
int dp[11][100005];
int main()
{int a[12],k=0;while(~scanf("%d%d%d%d%d%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6],&a[7],&a[8],&a[9],&a[10])){int sum=0;memset(dp,0,sizeof(dp));for(int i=1;i<=10;i++)sum+=a[i]*i;if(sum==0) break;for(int i=1;i<=10;i++){for(int j=0;j<=sum/2;j++){int tmp=dp[i-1][j];for(int l=1;l<=j/i&&l<=a[i];l++)tmp=max(tmp,dp[i-1][j-l*i]+l*i);dp[i][j]=tmp;}}if(dp[10][sum/2]*2==sum) printf("#%d:Can be divided.\n\n",++k);else printf("#%d:Can't be divided.\n\n",++k);}
}
