题目描述

小蓝正在一个瓜摊上买瓜。

瓜摊上共有 $n$ 个瓜，每个瓜的重量为 $A_i$。

小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。

小蓝希望买到的瓜的重量的和恰好为 $m$。

请问小蓝至少要劈多少个瓜才能买到重量恰好为 $m$ 的瓜。

如果无论怎样小蓝都无法得到总重恰好为 $m$ 的瓜，请输出 −1。

输入格式

输入的第一行包含两个整数 $n, m$，用一个空格分隔，分别表示瓜的个数和小蓝想买到的瓜的总重量。

第二行包含 $n$ 个整数 $A_i$，相邻整数之间使用一个空格分隔，分别表示每个瓜的重量。

输出格式

输出一行包含一个整数表示答案。

数据范围

对于 $20\%$ 的评测用例，$∑n ≤ 10$；
对于 $60\%$ 的评测用例，$∑n ≤ 20$；
对于所有评测用例，$1 ≤ n ≤ 30$，$1 ≤ A_i ≤ 10^9$，$1 ≤ m ≤ 10^9$。

输入样例：

3 10
1 3 13

输出样例：

2

算法

(暴力枚举) $O(n^2)$

剪枝时多加一个counter会好很多

时间复杂度

write here…

空间复杂度

write here…

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=31;
double a[N];
double sum[N];
typedef long long ll;
ll numSum;
int n,m,cnt,res=1e9;
int counter;
void dfs(int i,double s,int counter){
    cnt++;
//    cout<<sum[i]<<' '<<s<<endl;
    if(s==0) {res=min(res,counter);return;}
    else if(s>sum[i]||i==n||cnt>1e8||counter>res||s<0){return ;}
    else {
        dfs(i+1,s,counter),dfs(i+1,s-a[i],counter),dfs(i+1,s-a[i]/2,counter+1);}
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>a[i],numSum+=a[i];
    sort(a,a+n,greater<int>());
    sum[0]=numSum;
    for(int i=1;i<n;i++)
        sum[i]=sum[i-1]-a[i-1];//cout<<sum[i]<<' ';
    dfs(0,m,0);
    if(res>1e8)res=-1;
    cout<<res;
}