题目描述
商场一共 个物品，第
件物品的价格为
，每件物品只能买一件，你手上有
块钱。
求最多支出多少钱。
输入格式
第一行两个整数 。
接下来 个整数，表示
。
输出格式
输出最多支出是多少钱。
样例
样例 1 输入
3 10
1 2 3
样例 1 输出
6
样例 2 输入
4 10
4 3 5 11
样例 2 输出
9
数据范围与提示
对于 的数据，
。
对于 的数据，
。
对于 的数据，
。
对于 的数据，
。
标程
#include <bits/stdc++.h>
using namespace std;
const int maxn=1.3e6;
int n,m,v,u,a[maxn],b[2],c[2][maxn];
void dfs(int bo,int x,int t,int s) {
//所有的价值组合
if(x>t) {
c[bo][++b[bo]]=s;
return;
}
dfs(bo,x+1,t,s);
dfs(bo,x+1,t,s+a[x]);
}
int main() {
cin>>n>>m;
u=n>>1;
for(int i=1; i<=u; i++)cin>>a[i];
dfs(0,1,u,0);
v=n-u;
for(int i=1; i<=v; i++)cin>>a[i];
dfs(1,1,v,0);
sort(c[1]+1,c[1]+b[1]+1);
int ans=0;
for(int i=1; i<=b[0]; i++) {
int x=upper_bound(c[1]+1,c[1]+b[1]+1,m-c[0][i])-c[1]-1;
ans=max(ans,c[0][i]+c[1][x]);
}
cout<<ans<<endl;
return 0;
}
