题意：
首先t组数据 （t<=5），一个n代表有n件东西，每个东西可以代表两个物品，商品或者袋子，每个都有个值，如果这个要代表袋子的话，当前就代表是容量，而且必须把其他几件不是袋子的物品放一些进来，容量必须正好装满，问你有多少种合法的方案，袋子中放入的物品不同也代表不同，同一件物品只能放入一个袋子
（n<=15）
Sample Input
3
3
1 1 1
5
1 1 2 2 3
10
1 2 3 4 5 6 7 8 9 10
Sample Output
7
15
127
思路：首先我们看数据范围我们就能想到是状压DP，但是我们不能直接去0 1代表哪些是背包物品，这样我们就不确定物品怎么放入背包，所以我们预处理，我们预处理出所有状态是否可以是一个已经放满的背包，并且枚举状态中哪一个才是背包，为了方便计算
weight[i] 代表 该状态下所有物品的值的和
f[i] 代表该状态下 可以是一个放满的背包的种数
dp[i] 代表 该状态下合法的所有种数
我们可以利用weight 计算出 f[i],即我们枚举到当前位时，我们假设当前位是背包 weight[i]-a[i]==a[i] 如果是的话 f[i]++, 因为当前背包容量是a[i]，其他总和也是a[i]，即代表当前背包装满了
然后我们可以利用所有的单个装满的背包合并起来算出最后状态
#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-6 #define MOD 16007 #define INF 0x3f3f3f3f #define N 16 #define LL long long using namespace std; int a[N]; int f[1<<N];//组成袋子的合法方案数 int dp[1<<N];//合法方案数 int weight[1<<N];//第i种状态的重量 int main() { int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=0;i<(1<<n);i++){ weight[i]=0; f[i]=0; dp[i]=1; } for(int i=1;i<=n;i++)//n位数字 for(int j=1;j<(1<<n);j++)//2^n种状态 if( 1<<(i-1) & j )//若第i位是1 weight[j]+=a[i];//记录第j个状态的重量 for(int i=1;i<=n;i++)//n位数字 for(int j=1;j<(1<<n);j++)//2^n种状态 if( 1<<(i-1) & j )//若第i位是1 if(weight[j]-a[i]==a[i])//如果第j个状态的重量减去第i个物品的重量等于第i个物品的重量说明选择第j个状态是一个合法的袋子 f[j]++; for(int i=1;i<(1<<n);i++){//包裹2^n种状态 int k=(1<<n)-1-i;//与i相斥的状态 for(int j=k;;j=(j-1)&k){//选物品的状态且其不能选为包裹 dp[i|j]+=dp[j]*f[i]; if(j==0) break; } } printf("%d ",dp[(1<<n)-1]); } return 0; }