题解：AT_arc017_3 [ARC017C] 無駄なものが嫌いな人

思路

一看就是背包裸题

注意到本题数据范围 $1\le X\le 10^9$，所以我们肯定不能用暴搜，考虑折半搜索。我们可以先枚举前 $\frac{n}{2}$ 个物体所占体积的情况，再去枚举剩下物体所占体积的情况，统计体积和恰好为 $X$ 的情况。

这样我们可以把前半段搜出的结果存到 map 中，最后将后半段搜索结果恰好装满的情况累加，这个题就做完了。

code

#include<bits/stdc++.h>
using namespace std;
int n,x,ans,t,a[114],k;
map<int,int> m;
int main(){
	cin>>n>>x;
	k=n/2;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<(1<<k);i++){  //前半段
		t=0;
		for(int j=0;j<k;j++)
			if(1&(i>>j))
				t+=a[j];  
		m[t]++; 
	}
	for(int i=0;i<(1<<(n-k));i++){ //后半段
		t=0;
		for(int j=0;j<n-k;j++) 
			if(1&(i>>j))
				t+=a[j+k];  
		if(t<=x) ans+=m[x-t]; //统计
	}
	cout<<ans;
	return 0;
}