題目描述

商場一共 個物品，第 件物品的價格為 ，每件物品只能買一件，你手上有 塊錢。
求最多支出多少錢。

輸入格式

第一行兩個整數(shù) 。
接下來 個整數(shù)，表示 。

輸出格式

輸出最多支出是多少錢。

樣例

樣例 1 輸入

3 10
1 2 3

樣例 1 輸出

6

樣例 2 輸入

4 10
4 3 5 11

樣例 2 輸出

9

數(shù)據(jù)范圍與提示

對于 的數(shù)據(jù)， 。
對于 的數(shù)據(jù)， 。
對于 的數(shù)據(jù)， 。
對于 的數(shù)據(jù)， 。

標程

#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;
}