买瓜（dfs+剪枝）

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

样例输入

3 10
1 3 13

样例输出

提示

对于 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;
}