Candy （位压缩dp）

Candy

Time Limit:1000MS  Memory Limit:65535KB

Description:

Solo和koko是两兄弟，妈妈给了他们一大袋糖，每块糖上都有自己的重量。现在他们想要将这些糖分成两堆。分糖的任务当然落到了大哥Solo的身上，然而koko要求必须两个人获得的糖的总重量“相等”（根据Koko的逻辑），要不然就会哭的。
 非常不幸的是，koko还非常小，并且他只会先将两个数转成二进制再进行加法，而且总会忘记进位。如当12（1100）加5（101）时：
   1100
+ 0101
 ------
   1001
  于是koko得到的计算结果是9（1001）。此外还有一些例子：
5 + 4 = 1
7 + 9 = 14
50 + 10 = 56
（事实上，这正是异或运算:12^5=9,5^4=1…）
现在Solo非常贪婪，他想要尽可能使自己得到的糖的总重量最大，且不让koko哭。

Input:

输入的第一行是一个整数N(2 ≤ N ≤ 15)，表示有袋中多少块糖。第二行包含N个用空格分开的整数C_i(1 ≤ C_i ≤ 10⁶)，表示第i块糖的重量。

Output:

如果能让koko不哭，输出Solo所能获得的糖的总重量，否则输出“NO”。

分析：

一开始想了好久，还是感觉要爆搜，突然看到N只有15 ， 可以用位压缩，那么就自然的想到用dp求出所有可能了，当然，关键就在于重叠子问题了，用第i位表示是否选了第i个糖

#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
struct state
{
    int s, sum;
    //s:糖果的异或值,sum:糖果的实际总重量
} dp[1<<16];
int w[16];
int main()
{
    int n, tt = 0, ss = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &w[i]);
        tt ^= w[i];//所有糖果的异或值
        ss += w[i];//所有糖果的总质量
    }
    dp[0].s = dp[0].sum = 0;
    for(int i = 1; i <= (1 << n) - 1; i++)
        dp[i].s = dp[i].sum = -1;
    int ans = -1;
    for(int i = 0; i < n; i++)//枚举糖果数
    {
        for(int j = (1 << n) - 1 ; j >= 0; j--)//枚举所有状态
        {
            if(dp[j].sum == -1)
                continue;
            for(int k = 0; k < n; k++)
            {
                if(j&(1 << k))
                    continue;
                int t = j | (1 << k);
                dp[t].s = dp[j].s ^ w[k];
                dp[t].sum = dp[j].sum + w[k];
                if((tt ^ dp[t].s) == dp[t].s && (ss - dp[t].sum) && dp[t].sum)//注意异或运算的性质，同时不可能分到糖果数为0
                {
                    ans = max(dp[t].sum, ans);
                }
            }
        }
    }
    if(ans == -1)
        puts("NO");
    else printf("%d\n", ans);
}