蓝桥杯刷题-16-买瓜-DFS+剪枝优化⭐⭐

蓝桥杯2023年第十四届省赛真题-买瓜
在这里插入图片描述

在这里插入图片描述

该如何剪枝呢？⭐⭐

如果当前方案的切的刀数，已经大于等于了之前已知合法方案的最优解，那么就没必要
往后搜了。
如果后面的瓜的总和加起来，再加上当前已有的重量，都不到m,那么也没有必要搜索了。
如果你当前已有的重量超过了m,那么说明当前方案非法，直接return就好了。
n个瓜遍历结束，你肯定要return。
我们将瓜从大到小排序，这是一个贪心。

这个代码有可能超时：

#include <iostream>
#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=100;
double a[N];
double s[N];
int n,m;
int ans=INF;当前合法方案的最小值。
void dfs(int u,double w,int cnt){
  if(w==m){
    ans=min(ans,cnt);
    return;
  }

  //剪枝
  //如果n个瓜都遍历完了，那就返回。
  if(u>=n)return;

  //如果当前方案并不优于已有的合法答案，那就返回。
  if(cnt>=ans)return;

  //如果总重量已经超了，那么当前方案不合法。
  if(w>m)return;
  //如果后面的瓜所有重量加起来，都小于m，则当前方案不合法。
  if(w+s[u]<m)return;

  //选，但不切
  dfs(u+1,w+a[u],cnt);
  //选，切
  dfs(u+1,w+a[u]/2.0,cnt+1);
  //不选
  dfs(u+1,w,cnt);
}
bool cmp(int x,int y){
  return x>y;
}
void solve(){
  cin>>n>>m;

  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  sort(a,a+n,cmp);
  //后缀和
  for(int i=n-1;i>=0;i--){
    s[i]=s[i+1]+a[i];
  }
  dfs(0,0.0,0);
  if(ans==INF)ans=-1;
  cout<<ans<<endl;



}
signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  t=1;
  //cin>>t;
  while(t--)
  solve();
}