[YbtOJ Dfs] 最大费用

题目描述

商场一共 个物品，第 件物品的价格为 ，每件物品只能买一件，你手上有 块钱。
求最多支出多少钱。

输入格式

第一行两个整数 。
接下来 个整数，表示 。

输出格式

输出最多支出是多少钱。

样例

样例 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;
}