#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;
}
标签:cnt,return,int,sum,买瓜,dfs,当前
From: https://blog.csdn.net/weixin_73214301/article/details/137560994