yeqiu

用户名：dotcpp0718185

访问量：2559

签　名：

永远相信美好的事情即将发生！

等　　级
排　　名	28333
经　　验	493
参赛次数	0
文章发表	3
年　　龄	20
在职情况	学生
学　　校	华中师范大学
专　　业	计算机科学与技术

　　自我简介：

算法小白一枚~

TA的其他文章

根据公式找规律
浏览：211

颜色平衡树（dfs后序遍历）
浏览：1471

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

dfs搜索+剪枝

　　作者: yeqiu　　　　发表时间：2024-01-13 16:07:41 浏览：1461　|　评论：8　

原题链接：蓝桥杯2023年第十四届省赛真题-买瓜

对于每一个瓜有三种选择:
1)买整个瓜
2)买半个瓜，需要增加劈瓜次数
3)不买

则可以使用深度优先搜索解决, 对每个瓜的三种选择进行搜索, 解空间树是一颗完全三叉树, 时间复杂度为O(3^n), 肯定会超时, 故需要进行剪枝。

买半个瓜时需要将重量除2，会产生小数，故可以将重量数组都乘2，最大重量也乘2。

搜索时需要记录三个状态，当前层数pos，当前总重量sum，当前劈瓜的次数cnt，以下情况需要剪枝：
1）当前劈瓜次数大于已求得的最小次数，即cnt>ans
2）当前重量之和大于要求的重量，即sum>m

但是这样仍然会超时，还可以将重量数组降序排列，使得更快剪枝。还可以创建一个重量数组的后缀数组suf，这样在搜索时可以利用其剪枝：若当前重量加上剩余的所有瓜重量之和小于要求的重量，剪枝。

```
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 30; 
int INF = 100;

int n,m;
int v[N]; //重量数组
long suf[N+1]; //重量数组的后缀数组
int ans = INF; //将结果初始化为INF

/*
dfs搜索,参数分别表示当前层数,当前重量之和,切瓜的次数
*/
void dfs(int pos,long sum,int cnt){
    if(sum==m){ //找到了一个结果
        ans = min(ans,cnt);
        return;
    }
    //剪枝
    if(pos>=n || cnt>=ans || sum>m || sum+suf[pos]<m) return;
    //对三种选择进行搜索
    dfs(pos+1,sum+v[pos],cnt); 
    dfs(pos+1,sum+v[pos]/2,cnt+1);
    dfs(pos+1,sum,cnt);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    cin>>n>>m;
    m*=2; //总重量乘2
    for(int i=0;i<n;i++) cin>>v[i],v[i]*=2;
    sort(v,v+n,greater<int>());
    for(int i=n-1;i>=0;i--) suf[i] = suf[i+1]+v[i];
    dfs(0,0,0);
    
    if(ans==INF) cout<<-1;
    else cout<<ans;
    return 0;
}
```

0.0分

38 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

Astronomy

nb

2024-03-27 00:11:01

Dijkstra

nb

2024-03-22 11:05:45

裴卡咯

nb

2024-03-17 22:02:28

uq_95708158911

nb

2024-03-11 15:02:25

nb

2024-03-06 16:32:54

nb

2024-03-04 21:52:43

handsome慢

nb

2024-02-22 16:14:58

ieykzhou

思路太棒了！

2024-01-26 19:46:00

yeqiu

TA的其他文章

你可能喜欢

C二级辅导-等差数列（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

整人!!

A+B for Input-Output Practice (VII) （C语言代码）

人见人爱A+B （C语言代码）

dfs搜索+剪枝

评论区

精彩推荐

C语言训练-委派任务* （C语言代码）..................竟然是第一个

C语言程序设计教程（第三版）课后习题3.7 （C++代码）

简单的a+b （C语言代码）

母牛的故事（C语言代码）

剪刀石头布（C语言代码）

数字游戏（C++代码）

数组与指针的问题

敲七（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

P1003 （Java代码）

yeqiu

TA的其他文章

你可能喜欢

C二级辅导-等差数列 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

整人!!

A+B for Input-Output Practice (VII) （C语言代码）

人见人爱A+B （C语言代码）

dfs搜索+剪枝

评论区

精彩推荐

C语言训练-委派任务* （C语言代码）..................竟然是第一个

C语言程序设计教程（第三版）课后习题3.7 （C++代码）

简单的a+b （C语言代码）

母牛的故事 （C语言代码）

剪刀石头布 （C语言代码）

数字游戏 （C++代码）

数组与指针的问题

敲七 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

P1003 （Java代码）

C二级辅导-等差数列（C语言代码）

　　评论区

母牛的故事（C语言代码）

剪刀石头布（C语言代码）

数字游戏（C++代码）

敲七（C语言代码）