目录
问题描述：
小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜，每个瓜的重量为 Ai 。 小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈 一刀。 小蓝希望买到的瓜的重量的和恰好为m。 请问小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小 蓝都无法得到总重恰好为 m 的瓜，请输出 −1 。
输入格式：
输入的第一行包含两个整数 n, m，用一个空格分隔，分别表示瓜的个数和 小蓝想买到的瓜的总重量。 第二行包含 n 个整数 Ai，相邻整数之间使用一个空格分隔，分别表示每个 瓜的重量。
输出格式：
输出一行包含一个整数表示答案。
评测用例规模与约定： 对于20%的评测用例，1≤n ≤10 ; 对于60%的评测用例，1≤n ≤20 ; 对于100%的评测用例，1≤n≤30，1≤Ai≤10^9，1 ≤m≤ 10^9。方法一：dfs暴力模拟（45%）
将所有瓜按顺序排成一排，从前往后选择每个瓜。对于每一个瓜，有三种选择：不要，切一半，拿整个。分别切了0,1,0刀。不能切一刀之后两半全拿，这样不符合题意的最少劈的次数。 可以使用dfs模拟这个从前往后选择的过程，dfs(id,sum,cut)中的三个参数分别表示当前选择的是第几个瓜，之前一共拿了多少重量的瓜，之前一共劈了多少刀。上面说的三种选择对应的函数就是: 1、不拿dfs(id+1,sum,cut) 2、切一刀，拿一半dfs(id+1,sum+a[id]/2,cut) 3、不切，拿整个dfs(id+1,sum+a[id],cut) 当sum==想要的重量的m时，就可以比较当前劈的次数与之前最少的次数哪个更小了。#include <iostream>
using namespace std;
double a[35];
int n,m;
int ans=35;
void f(int id,double sum,int cut)//当前选择第几个瓜，已拿重量，已劈次数
{
if(sum==m)//拿够了
{
ans=min(ans,cut);
return ;
}
if(id>n) return ;//所有瓜都选择完了
f(id+1,sum,cut);//不拿这个瓜
f(id+1,sum+a[id]/2,cut+1);//切一刀，拿一半
f(id+1,sum+a[id],cut);//不切，拿整个
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
f(1,0,0);
if(ans<35) cout<<ans;
else cout<<"-1";
return 0;
}方法二：dfs剪枝（100%）
分析上一个代码，当n=30时执行了3^30次dfs函数，其中有很多情况是不需要执行的。剪枝有以下几种思路：
1、当前获得的总重量已经超过目标m，不需要继续执行。
2、当前劈的次数超过了目前最少的次数，不需要继续执行。
3、如果之后所有的瓜全部都要，加上当前的重量，也不能达到目标m，不需要继续执行。为了快速计算之后所有瓜的重量，可以使用前缀和预处理瓜的重量。为了更早进行剪枝，可以将瓜的重量从大到小排序。
#include <iostream>
#include<algorithm>
using namespace std;
double a[35];
double b[35];
int n,m;
int ans=35;
void f(int id,double sum,int cut)//当前选择第几个瓜，已拿重量，已劈次数
{
if(sum==m)//拿够了
{
ans=min(ans,cut);
return ;
}
if(id>n) return ;
if(sum>m||cut>ans) return ;
if(sum+b[n]-b[id-1]<m) return ;//剩下的瓜全拿，也不够目标重量
f(id+1,sum,cut);//不拿这个瓜
f(id+1,sum+a[id]/2,cut+1);//切一刀，拿一半
f(id+1,sum+a[id],cut);//不切，全拿
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1,greater<double>());//从大到小排序
for(int i=1;i<=n;i++)
b[i]=a[i]+b[i-1];//前缀和预处理
f(1,0,0);
if(ans<35) cout<<ans;
else cout<<"-1";
return 0;
}注意需要将瓜的重量除以2，直接用int型/2是整除应该使用double型，或者将所有瓜的重量和m都乘以2，由于数据范围时10^9，最好使用long long型。
我在写这个题的时候将数组下标从1开始存，排序的时候sort第二个参数应该加n+1，因为这里写错了导致卡了很久，去读了官方这题的题解感觉很奇怪，将瓜分成两部分分别dfs，后一部分dfs时再二分搜索前一部分存的对应重量的刀数相加。
标签：重量,组第,cut,int,题解,sum,dfs,蓝桥,id From： https://blog.csdn.net/qq_40485202/article/details/137084596