【16届蓝桥杯寒假刷题营】第2期DAY2
1.快快变大 - 蓝桥云课
问题描述
小蓝非常喜欢数字，特别是大的数，但是对于超过一定界限的数，小蓝则会非常讨厌他，现在给定你 n 个数，以及一个上界 k，定义小蓝的喜爱值为选出的所有数的和，求小蓝的最大喜爱值为多少？
输入格式
第一行给定两个整数 n,k 表示共有 n 个数字以及上界 k。
第二行给定 n 个数，表示数的大小。
输出格式
输出一个整数表示小蓝的最大喜爱值。
输入案例
5 10
1 2 3 4 5样例输出
16评测数据规模
对于 100% 的评测数据：1≤n≤44，0≤k≤1e9。
思路：
代码如下：
爆搜：
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,k;
const ll N = 1e3+10;
ll arr[N];
ll ans = -1e9;
void dfs(ll x, ll sum)
{
if(sum > k)
return;
if(x > n)
{
if(sum <= k)
{
ans = max(ans,sum);
}
return;
}
dfs(x+1,sum+arr[x]);
dfs(x+1,sum);
}
int main(void)
{
cin >> n >> k;
for(ll i = 1 ; i <= n ; i++)
cin >> arr[i];
dfs(1,0);
cout << ans;
return 0;
}