c++解决买瓜问题，回溯算法

解题思路:将瓜从大到小排序，以获得最小切割次数，采用回溯算法来判断切割次数

注意事项:由于采用float定义会产生精度误差，所以采用*2的方式

参考代码:

#include

#include

#include

using namespace std;

vector

vector

int ans=31;

int m;

long sum=0;

int n;

bool cmp(int a,int b){

return a>b;

}

void dfs(int i,int count,long sum)

{

if(sum==m){

ans=min(count,ans);//找到最小次数返回

return;

}

if(sum>m||i>n||count>=ans||sum+B[i]<m)return;//减少次数，不然要超时

dfs(i+1,count,sum+M[i]);//直接买整个

dfs(i+1,count+1,sum+M[i]/2);//买半个

dfs(i+1,count,sum);//不买

}

int main()

{

long totle=0;

cin>>n>>m;

m*=2;

for(int i=0;i<n;i++)

{

cin>>M[i];

M[i]*=2;

totle+=M[i];

}//全部以两倍储存，用float容易出错

for(int i=n-1;i>=0;i--){

B[i]=B[i+1]+M[i]; 

}

if(totle<m){

cout<<-1;

return 0;

}

sort(M.begin(),M.end(),cmp);

dfs(0,0,sum);

if(ans!=31)cout<<ans;//如果ans的数值改变就输出，否则说明找不到，输出-1

else cout<<-1;

return 0;

 }