題意：

給你一個集合N（N<=35）,問集合的子集，除了空集，使得自己中所有元素和的絕對值最小，若存在多個值，那么選擇子集中元素最少的那個。

題目：

Given a list of N integers with absolute values no larger than $10^{15}$, 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 1015 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

分析：

1.n 最大到 35，每個數有選、不選兩種可能，最多有 $2^{35}$ 個子集,因此暴力枚舉的話，一定會Time Limit Exceed，采用折半枚舉的思想，分成兩個集合，這樣每邊最多 18 個元素，分別進行枚舉，復雜度降到 $2^{18}$
2.利用二進制將和以及元素個數存在兩個數組中，先預判是否滿足題意，再將其中一個元素和取相反數后排序，因為總元素和越接近零越好，再二分查找即可，用lower_bound時考慮查找到的下標和他前一個下標，比較元素和以及元素個數，不斷更新即可。
3.由于是求大數的絕對值，此時需要開函數，（不知道為什么，我調用labs函數，結果是錯誤的，所以自己寫了一個）
4.然后枚舉其中一個子集，排序后暫存后，再枚舉另一個子集，通過二分查找第一個集合中與該值的相反數最接近的元素，要注意的是如果有多個元素與相反值最接近，取數的個數最小的那一個。
5.與尋找合適的子集并與第一個集合的子集相加，從而找到絕對值最小的子集.
下面附上AC代碼，里面注解有部分解答。

AC代碼：

#include<stdio.h> #include<map> #include<string.h> #include<math.h> #include<algorithm> #include<iostream> #define inf 0x3f3f3f3f3f3f3f3f using namespace std; typedef long long ll; const int M=50; int n,cnt=0; map<ll,ll> vis; ll Labs(ll x){if(x>0) return x;return -x; } ll a[M],dp[1<<20],ans;//vis當前所選的最少個數,dp數組存儲前一半的值，ans是最終結果 ll solve(ll num) {if(num<=dp[1])return dp[1];else if(num>=dp[cnt])return dp[cnt];int mid=upper_bound(dp+1,dp+cnt+1,num)-dp;if(Labs(dp[mid]-num)==Labs(dp[mid-1]-num)){if(vis[dp[mid-1]]<vis[dp[mid]])return dp[mid-1];return dp[mid];}else if(Labs(dp[mid]-num)>Labs(dp[mid-1]-num))return dp[mid-1];return dp[mid]; }//查找與x最接近的元素，要注意的是如果有多個元素與x最接近，取數的個數最小的那一個 int main() {while(~scanf("%d",&n)&&n){cnt=0,ans=inf;vis.clear();memset(a,0,sizeof(a));memset(dp,0,sizeof(dp));for(int i=1; i<=n; i++)scanf("%lld",&a[i]);if(n==1){printf("%lld 1\n",Labs(a[1]));continue;}int x=n/2,y=n-x;int mi=(1<<x)-1;/*mi為所選元素的所有可能性，除去空集*/ll id=inf;for(int i=1; i<=mi; i++){ll now=0,tot=0;for(int j=1; j<=x; j++){if(i&(1<<(j-1)))/**枚舉i為多少種方式，j為多少個數，用j來控制位數，i控制方式*/now+=a[j],tot++;}if(vis[now])vis[now]=min(vis[now],tot);//如果當前值已經出現過，元素個數取較小的elsevis[now]=tot,dp[++cnt]=now;//沒有出現過，建立映射關系if(Labs(now)<ans){ans=Labs(now);id=tot;}//如果答案更優，更新答案else if(Labs(now)==ans)id=min(id,tot);//如果答案相同，元素個數取較小的}sort(dp+1,dp+cnt+1);for(int i=1; i<=(1<<y)-1; i++){ll now=0,tot=0;for(int j=1; j<=y; j++)if(i&(1<<(j-1)))now+=a[j+n/2],tot++;if(Labs(now)<ans){ans=Labs(now);id=tot;}else if(Labs(now)==ans)id=min(id,tot);ll num=solve(-now);//二分找到與相反數最接近的數if(ans>Labs(num+now)){ans=Labs(num+now);id=tot+vis[num];}else if(ans==Labs(num+now))id=min(id,tot+vis[num]);}printf("%lld %d\n",ans,id);}return 0; }

總結

以上是生活随笔為你收集整理的Subset POJ - 3977（折半枚举+二分+二进制枚举）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。