买瓜（dfs+剪枝）
题目描述
小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜，每个瓜的重量为 Ai 。
小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。
小蓝希望买到的瓜的重量的和恰好为 m 。
请问小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小蓝都无法得到总重恰好为 m 的瓜，请输出 −1 。
输入格式
输入的第一行包含两个整数 n, m，用一个空格分隔，分别表示瓜的个数和小蓝想买到的瓜的总重量。
第二行包含 n 个整数 Ai，相邻整数之间使用一个空格分隔，分别表示每个瓜的重量。
输出格式
输出一行包含一个整数表示答案。
样例输入
3 10 1 3 13
样例输出
2
提示
对于 20% 的评测用例，∑n≤10；
对于 60% 的评测用例，∑n≤20；
对于所有评测用例，1 ≤n≤30，1≤ Ai ≤ 10^9 ，1 ≤ m ≤ 10^9
思路：
使用深度优先搜索解决, 对每个瓜的三种选择进行搜索, 解空间树是一颗完全三叉树, 时间复杂度为O(3^n), 肯定会超时, 故需要进行剪枝。
买半个瓜时需要将重量除2，会产生小数，故可以将重量数组都乘2，最大重量也乘2。
搜索时需要记录三个状态，当前层数pos，当前总重量sum，当前劈瓜的次数cnt，以下情况需要剪枝：
1）当前劈瓜次数大于已求得的最小次数，即cnt>ans
2）当前重量之和大于要求的重量，即sum>m
但是这样仍然会超时，还可以将重量数组降序排列，使得更快剪枝。还可以创建一个重量数组的后缀数组suf，这样在搜索时可以利用其剪枝：若当前重量加上剩余的所有瓜重量之和小于要求的重量，剪枝。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=33;
double a[N];
double s[N];
bool st[N];
int n;
double m;
int cnt=1e9;
//三种状态 整个 一半 不要
//dfs+剪枝
//参数 当前层数 当前的西瓜的总重量 当前切了多少次
void dfs(int pos,double sum,int num)
{//当sum==m时 取最小的 返回上一层 if(sum==m){cnt=min(cnt,num);return ;}//剪枝 sum+s[n]-s[pos-1] 是求当前sum加上之后所有的数均不能组成时 剪枝一下 if(sum>m||pos>n||cnt<=num||sum+s[n]-s[pos-1]<m) return ;dfs(pos+1,sum+a[pos],num);//整个要 dfs(pos+1,sum+(a[pos]/2),num+1);//半个 dfs(pos+1,sum,num);//都不要
}
//从大到小排 尽量减少切一半的次数
double cmp(double x,double y)
{return x>y;}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++) {cin>>a[i];}//排序 从大到小排 sort(a+1,a+1+n,cmp);//求前缀和 for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];dfs(1,0,0);if(cnt==1e9) cout<<"-1"<<endl;else cout<<cnt<<endl; return 0;
}