买瓜-dfs

6.买瓜 - 蓝桥云课 (lanqiao.cn)

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,m,a[35],cnt=40,sum[35];
//x是当前编号,w是当前总重量,c是当前劈了多少个瓜
void dfs(int x,int w,int c){
	if(w==m){//如果当前重量符合要求了，就更新一下是不是最小值，然后退出
		cnt=min(cnt,c);
		return;
	}
	if(x>=n) return;//当前的所有瓜都遍历一遍了，就退出
	if(w>m) return;//当前的重量超了，就退出
	if(c>=cnt) return;//当前劈的瓜的数量超过目前的答案了，再继续下去也不是最优解了，就退出
	if(w+sum[n-1]-sum[x-1]<m) return;//当前剩下的没遍历的瓜，就算都算上也达不到所要求的重量就退出
	//注意，下面三个dfs的顺序，重量最多的(因为最有可能是最优解)最先进行dfs
	dfs(x+1,w+a[x],c);//当前的瓜不劈开
	dfs(x+1,w+a[x]/2,c+1);//当前的瓜劈开
	dfs(x+1,w,c);//当前的瓜不买
}
bool cmp(int a,int b){
	return a>b;
}
void solve(){
	cin>>n>>m;
	//这里和下面乘以2，是因为劈一刀，有可能是小数，有小数点0.5，乘以2把小数点去掉
	//方便上面dfs的w==m判断相等，float和double我怕精度原因不相等，乘以2就可以整数int判断相等了
	m=m*2;
	for(int i=0;i<n;i++){
		cin>>a[i];
		a[i]*=2;
		//下面是前缀和，存到当前i的重量的累加值
		if(i>0)
			sum[i]=sum[i-1]+a[i];
		else
			sum[i]=a[i];
	}
	sort(a,a+n,cmp);//排序一下，从大到小排序，dfs的时候就能从大到小，这样求最优解更快
	dfs(0,0,0);
	if(cnt==40){//如果没找到答案，即cnt还是初始值
		cout<<-1;
	}
	else cout<<cnt;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie();
	cout.tie();
	solve();
	return 0;
}