2018.08.10 atcoder Median Sum（01背包）

传送门
题意简述：输入一个数组anan。
对于所有2n−12n−1个非空子集，每个子集的权值是包含的所有元素之和。
求这2n−12n−1个非空子集权值的中位数。
对于每个权值vv都有一个对应的”补集”tt满足v+t=sumv+t=sum，就是说集合中找个断点两边两个权值相加都是整个集合的和。
因此可以根据中位数的定义跑一遍01背包找出中位数。
代码：

#include<bits/stdc++.h> using namespace std; int sum=0,n,x; bitset<5000000>s; int main(){scanf("%d",&n),s[0]=1;for(int i=1;i<=n;++i)scanf("%d",&x),s|=s<<x,sum+=x;for(int i=(sum+1)/2;;++i)if(s[i]){cout<<i;return 0;}return 0; }

转载于:https://www.cnblogs.com/ldxcaicai/p/9738389.html

总结

以上是生活随笔为你收集整理的2018.08.10 atcoder Median Sum（01背包）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。