块，现要将它们分成两部分，使得两部分价值之和相等，问是否可以实现。
其中大理石的总数不超过 20000
。
输入格式
输入包含多组数据！
每组数据占一行，包含 6
个整数，表示 a[1]∼a[6]。
当输入为 0 0 0 0 0 0 时表示输入结束，且该行无需考虑。
输出格式
每组数据输出一个结果，每个结果占一行。
如果可以实现则输出 Can，否则输出 Can't。
输入样例：
4 7 4 5 9 1
9 8 1 7 2 4
6 6 8 5 9 2
1 6 6 1 0 7
5 9 3 8 8 4
0 0 0 0 0 0
输出样例：
Can't
Can
Can't
Can't
Can 这题还是比较好写的
我最开始的时候都没看出来这是一个背包
先说说我想到的第一个思路吧
设f[a1][a2][a3][a4][a5][a6]表示在用了a1个1，a2个2·····a6个6的时候是否有可能能够划分为价值相等的两部分
转移就是尝试同时增加两部分价值相等的大理石，距离就是分解数字
比如6=3+3=3+2+1=4+2=2+2+2·····
很多，但是因为只到了6，就能够用类似打表的办法做出来
复杂度应该是O(a[1]*a[2]····*a[6])
直接爆炸
（可能是没睡好脑子不清醒吧。。想出了这么炸裂的做法）
正解
我们只要能够从这些石头里面选出来总价值为sum/2的组合，那就说明这些大理石肯定能够被成功划分（sum是所有大理石的价值和）
所以这就是一个可行性多重背包。。而且因为只有6种，复杂度降低了。。。
就是poj1742coins这题的弱化版
思路一模一样，既然我们已经不关心“最优解”而只关心“可行性”，那那些已知可行的状态自然是没有再转移过去的必要，硬币的数量也不需要浪费在这些情况上面了
感觉在写一次这种题目，有了些新的感受
这种转移的方式其实是为了这种题目专门设计的。。
而并不只是一个简单的改版
积累积累
code
#include<bits/stdc++.h> #define ll long long using namespace std; inline int read() { char c=getchar();int a=0,b=1; for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1; for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b; } bool f[120001];int a[7],used[120001]; int main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); while(1) { int sum=0; memset(f,0,sizeof(f)); for(int i=1;i<=6;i++) { a[i]=read(); sum+=a[i]*i; } if(sum==0)return 0; if(sum%2) { cout<<"Can't"<<endl; } else { f[0]=1; for(int i=1;i<=6;i++) { memset(used,0,sizeof(used)); for(int j=0;j<=sum/2;j++) { if(f[j]&&!f[j+i]&&used[j]<a[i]) { f[j+i]=1; used[j+i]=used[j]+1; } } } // for(int i=1;i<=sum/2;i++)cout<<f[i]<<' '; // cout<<endl; if(f[sum/2])cout<<"Can"<<endl; else cout<<"Can't"<<endl; } } return 0; }