子集问题。

题目：

Describe

　　Given a list of N integers with absolute values no larger than 10 ¹⁵, find a non empty subset of these numbers which minimizes the absolute value of the sum of its elements. In case there are multiple subsets, choose the one with fewer elements.

Input

The input contains multiple data sets, the first line of each data set contains N <= 35, the number of elements, the next line contains N numbers no larger than 10 ¹⁵ in absolute value and separated by a single space. The input is terminated with N = 0

Output

For each data set in the input print two integers, the minimum absolute sum and the number of elements in the optimal subset.

　　Sample Input

1
10
3
20 100 -100
0

　　Sample Output

10 1
0 2

分析：

　　题意挺简单的，虽然是英文，取集合的一个非空子集，使里面元素和绝对值最小，求最小的和的绝对值和此时可取的最小的s。

　　首先还是想最暴力的方法：直接枚举，2的35次方，显然会t掉但是貌似还行，可能还真和枚举有关，但是我们并不能直接枚举，怎么优化一下。

　　首先，我们想这样一个问题：如果我们的数据范围只有一半，我们会怎么做显然，我们就可直接枚举了，2¹⁸还是可以接受的，怎么枚举呢？当然直接算没问题（再乘一个18），其实还可以用一个类似dp的方法转移一下（当然要状态压缩啦），省的题目卡你。然后就是怎么算接下来的，这样的话我们还有一半没有选，不过我们仍然可以枚举，之后呢？再每个状态“配对”不还是卡死吗？其实并不用，我们把一边的状态排序，然后就可以直接枚举另一边的状态了，，然后再从这一边二分查找，完美解决问题。复杂度也可以，于是有人问：那为啥不直接枚举35个数然后二分找别的呢？二分是要排序的。。。直接卡死，数组都开不了。复杂度n*（2ⁿ+2^35-n）基本不等式求一下，什么时候最小就一目了然啦。

　　然后就是0处理好，这里数据好像并没有卡你，但是还是要处理一下的。

　　最小的处理怎么办呢？（见代码）

　　还有就是要自己想明白的就是一些细节了（详见代码）

　　还有就是自己写abs，要不就用cmath里的。要不就。。。

代码：

　　代码后面还有哦。

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
const int maxn=1<<18;
int z[maxn+10];
long long a[36];
struct J{
    long long val;
    int w;
    J(){
        w=val=0;
    }
    friend bool operator < (J a,J b){
        if(a.val==b.val)
            return a.w<b.w;
        return a.val<b.val;
    }
};
J ff[maxn];//前一半
J fz[maxn];//后一半
int w(int a){
    int ans=0;
    while(a){
        ans+=(a&1);
        a>>=1;
    }
    return ans;
}
int se(long long ke,int ma){//二分
    int l=0,r=(1<<ma)-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(fz[mid].val<ke)
            l=mid+1;
        else
            r=mid-1;
    }
    return r;
}
long long Abs(long long a){
    if(a>=0)
        return a;
    return -a;
}
int main(){
    int n;
    for(int i=0;i<=18;i++)
        z[1<<i]=i+1;
    while(~scanf("%d",&n)&&n){
        bool cl=1;
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            if(a[i]==0){
                printf("0 1
");
                cl=0;
            }
        }
        if(!cl)
            continue;
        int fb=n/2;
        long long ans=1e18;
        int s=40;
        ff[0].val=fz[0].val=fz[0].w=ff[0].w=0;
        for(int i=1;i<=(1<<fb)-1;i++){//类似dp的东西
            ff[i].val=ff[i^(i&(-i))].val+a[z[i&(-i)]];
            ff[i].w=w(i);
        }
        for(int i=1;i<=(1<<(n-fb))-1;i++){
            fz[i].val=fz[i^(i&(-i))].val+a[z[i&(-i)]+fb];
            fz[i].w=w(i);
        }
        sort(fz,fz+(1<<(n-fb)));
        for(int i=1;i<=(1<<(n-fb))-1;i++)
            if(fz[i].val==fz[i-1].val&&fz[i-1].w!=0)//最小的要求
                fz[i].w=fz[i-1].w;
        for(int i=0;i<=(1<<fb)-1;i++){
            int js=se(-ff[i].val,n-fb);
            for(int j=js-1;j<=js+2;j++)//想明白为什么是-1和+2，不放心的话就范围大一点。。。
                if(j<=(1<<(n-fb))-1&&j>=0&&(i||fz[j].w)){
                    if(ans>Abs(fz[j].val+ff[i].val)){
                        ans=Abs(fz[j].val+ff[i].val);
                        s=ff[i].w+fz[j].w;
                    }
                    else if(ans==Abs(fz[j].val+ff[i].val))
                        s=min(s,ff[i].w+fz[j].w);
                }
            if(i){//处理一下特殊的0
                if(Abs(ff[i].val)<ans){
                    ans=Abs(ff[i].val);
                    s=ff[i].w;
                }
                else if(Abs(ff[i].val)==ans){
                    s=min(s,ff[i].w);
                }
            }
        }
        printf("%lld %d
",ans,s);
    }
    return 0;
}

其他思路，分成两段处理不变，可不可以排序两边然后然后来跑一边呢，好像也是可以的。但是优势并不明显（多一个排序），大家可以试试。