题目：Dividing
题意：6种重量的的石头，每个给定数量，用总重的一半去装，问能否装满.
#include <iostream>#include <algorithm>#include <stdlib.h>#include <time.h>#include <cmath>#include <cstdio>#include <string>#include <cstring>#include <vector>#include <queue>#include <stack>#include <set>#define c_false ios_base::sync_with_stdio(false); cin.tie(0)#define INF 0x3f3f3f3f#define INFL 0x3f3f3f3f3f3f3f3f#define zero_(x,y) memset(x , y , sizeof(x))#define zero(x) memset(x , 0 , sizeof(x))#define MAX(x) memset(x , 0x3f ,sizeof(x))#define swa(x,y) {LL s;s=x;x=y;y=s;}using namespace std ;#define N 20005const double PI = acos(-1.0);typedef long long LL ;int dp[6*N];int i = 0;int W,a[10];void ZeroOnePack(int siz, int prise){for(int i = W;i>=siz;i--)dp[i] = max(dp[i], dp[i-siz] + prise);}void CompletePack(int siz, int prise){for(int i = siz; i<= W; i++)dp[i] = max(dp[i], dp[i-siz]+prise);}void MultiplePack(int siz, int prise, int num){if(siz*num >= W){CompletePack(siz,prise);return ;}int k = 1;while(k<num){ZeroOnePack(k*siz, k*prise);num-=k;k*=2;}ZeroOnePack(num*siz, num*prise);}bool cal(){if(W%2 == 0) W/=2;else return false;for(int i =1 ; i <= 6; i++ ){MultiplePack(i,i,a[i]);}if(dp[W] == W)return true;elsereturn false;}int main(void){//freopen("in.txt","r",stdin);while(cin>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6]){zero(dp);W = 0;for(int j = 1;j <= 6;j++){W+=j*a[j];}if(a[6]== 0 &&a[1] == 0 &&a[2] == 0&& a[3] == 0&& a[4] ==0&& a[5] ==0)break;printf("Collection #%d:\n",++i);if(cal())puts("Can be divided.\n");elseputs("Can't be divided.\n");}return 0;}
