买瓜（dfs+剪枝）

题���描述

（）

小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜，每个瓜的重量为 Ai 。

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

（）

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

请问小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小蓝都无法得到总重恰好为 m 的瓜，请输出 −1 。

输入格式

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

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

输出格式

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

样例输入

3 101 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#include#includeusing 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>n>>m;        for(int i=1;i>a[i];}//排序 从大到小排 sort(a+1,a+1+n,cmp);//求前缀和 for(int i=1;i