首页 > 其他分享 >dfs爆搜顺序与剪枝

dfs爆搜顺序与剪枝

时间:2023-01-22 22:44:48浏览次数:63  
标签:剪枝 cnt 顺序 小猫 int dfs ans return

dfs爆搜顺序与剪枝

小猫爬山

翰翰和达达饲养了 N只小猫,这天,小猫们要去爬山。

经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。

翰翰和达达只好花钱让它们坐索道下山。

索道上的缆车最大承重量为 \(W_i\),而 N 只小猫的重量分别是\(C_1,C_2,C_3...,C_N\)

当然,每辆缆车上的小猫的重量之和不能超过\(W\)。

每租用一辆缆车,翰翰和达达就要付1美元,所以他们想知道,最少需要付多少美元才能把这 N只小猫都运送下山?

输入格式

第 11 行:包含两个用空格隔开的整数,N和 W。

第 \(2..N+1\)行:每行一个整数,其中第 i+1行的整数表示第i只小猫的重量 \(C_i\)。

输出格式

输出一个整数,表示最少需要多少美元,也就是最少需要多少辆缆车。

数据范围

\(1\le N \le 18\)

\(1 \le C_i \le W_ \le 10^8\)

输入样例:

5 1996
1
2
1994
12
29

输出样例:

2

题目分析

  • 首先看题目数据范围就可以推断应该是用暴力搜索每种情况,得出最小值。
  • 确定是爆搜,那么我们就需要确定好一种正确的、容易实现的搜索顺序来不遗漏地覆盖每种情况,保证能得出最终的最小值。

具体实现

我们可以使用的搜索顺序为:枚举每一只小猫可以放到哪辆车上。

对于每一只猫来说, 都有以下两种大的选择方式:

  1. 放到现在已经有的一辆车上。
  2. 放到一辆新车上。

那么我们就可以按照这种搜索顺序来实现\(dfs\).

剪枝优化的可能

  1. 当有一种放置的方式在枚举过程中的车辆数\(cnt\)发现已经大于我们记录的答案\(ans\)时,我们知道cnt一定不是最终答案,便可以提前结束这次枚举。(最优性剪枝)
  2. 我们枚举时尽量搜索分支较少的节点,那么我们可以想到如果先选体重大的猫,就可以达到这种效果。如每辆车的限重为\(1996\),那么一只体重为\(1994\) 的猫一放上去,就只能再允许放体重不超过\(2\) 的猫了,显然分枝数就少了很多;如果先枚举的体重为\(1,2,3...\) 的猫的话,就可以有很多放置的可能性出现,显然会耗时不少。(搜索分枝少)

思路与代码结合

#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int cat[N];  // 每只猫的体重
int sum[N];  // 第i辆车现有的重量数
int n,m;
int ans=N; // 最终的答案,可知最差的情况为:每只猫放到一辆车上,即ans=猫的数量
bool cmp(int a,int b) 
{
    return a>b;
}
void dfs(int u,int cnt)
{
    if (cnt>=ans) return;
    if (u==n)
    {
        ans=cnt;
        return;
    }
    
    // 第一大类情况:不新开一辆车,从已有的车中选择
    
    for (int i=1;i<=cnt;i++)  // 目前有1——cnt共有cnt辆车可供选择放置
    {
        // 当前的车已有的重量加上想放置的猫的重量要不超过每辆车的重量上限
        if (sum[i]+cat[u]<=m)
        {
            sum[i]+=cat[u];
            dfs(u+1,cnt);  // 放置下一只猫,可供选择的车依然是cnt辆
            sum[i]-=cat[u];
        }
    }
    
    //第二大类情况:新开一辆车 
    sum[cnt+1]=cat[u];  
    dfs(u+1,cnt+1); 
    sum[cnt+1]=0;
}
int main()
{
    cin>>n>>m;
    for (int i=0;i<n;i++)
        cin>>cat[i];
    
    sort(cat,cat+n,cmp);
    dfs(0,0); // 从下标第0只猫中选,目前已有0辆车
    
    cout<<ans<<endl;
    return 0;
}

分成互质组

给定 n个正整数,将它们分组,使得每组中任意两个数互质。

至少要分成多少个组?

输入格式

第一行是一个正整数 n。

第二行是 n个不大于10000的正整数。

输出格式

一个正整数,即最少需要的组数。

数据范围

\(1\le n \le 10\)

输入样例:

6
14 20 33 117 143 175

输出样例:

3

题目分析

基本与小猫爬山的思想一致,不再赘述。思路确实很顺~

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int n;
int num[N];
vector<int>group[N]; // 记录第i组的每个数
int ans=N; 
int gcd(int a,int b)
{
    return b? gcd(b,a%b):a;
}
bool check(int u,int x) // 判断x是否与第u组的每个数都互质
{
    bool flag = false;
    for (auto t:group[u])
    {
        if (gcd(t,x)!=1)
        {
            flag = true;
            break;
        }
    }
    if (flag) return false;
    else return true;
}
void dfs(int u,int cnt)
{
    if (cnt>=ans) return;
    
    if (u==n)
    {
        ans=cnt;
        return;
    }
    
    for (int i=1;i<=cnt;i++)
    {
        if (group[i].size()>=1&&check(i,num[u]))
        {
            group[i].push_back(num[u]);
            dfs(u+1,cnt);
            group[i].pop_back();
        }
        
    }
    
    group[cnt+1].push_back(num[u]);
    dfs(u+1,cnt+1);
    group[cnt+1].clear();
}
int main()
{
    cin>>n;
    for (int i=0;i<n;i++)
        cin>>num[i];
    
    dfs(0,0);
    
    cout<<ans<<endl;
    return 0;
}	

标签:剪枝,cnt,顺序,小猫,int,dfs,ans,return
From: https://www.cnblogs.com/sdnu-dfl/p/17064755.html

相关文章

  • 03 顺序结构
    顺序结构packagecom.zhan.base_2;publicclassTest03_Sequence{publicstaticvoidmain(String[]args){inta=1;intb=2;intc......
  • 算法编程 dfs 从先序和中序遍历还原二叉树
    105.从前序与中序遍历序列构造二叉树给定两个整数数组 preorder和inorder ,其中 preorder是二叉树的先序遍历,inorder 是同一棵树的中序遍历,请构造二叉树并返回......
  • 接收一个整型值(无符号),按照顺序打印它的每一位。例如:1234,输出1 2 3 4
    例如:1234,输出1234 #include<stdio.h>voidprint(intn){if(n>9){print(n/10);}printf("%d",n%10);}intmain(){unsignedintnum=0;printf("请输入一......
  • 【DFS】LeetCode 951. 翻转等价二叉树
    题目链接951.翻转等价二叉树思路如果二叉树root1,root2根节点值相等,那么只需要检查他们的孩子是不是相等就可以了。如果root1或者root2是null,那么只有在他们都......
  • go打印fmt.Println指针的逃逸问题的注意,打印的顺序
    问题1:funcmain(){model.DBNew("./conf.toml")varuser[]model.CoreGrainedmodel.DB().Find(&user)for_,i:=rangeuser{vargg[]stringe......
  • 【DFS】LeetCode 101. 对称二叉树
    题目链接101.对称二叉树思路DFS递归解决代码classSolution{publicbooleanisSymmetric(TreeNoderoot){if(root==null){returnt......
  • Jmeter学习:控制器--顺序随机控制器
    一、顺序随机控制器功能:通过该组件,我们可以让控制器内部的逻辑随机执行一个,一般用来模拟业务的不确定性。随机控制器在线程迭代或者控制器循环的时候均会触发。  ......
  • 【DFS】LeetCode 226. 翻转二叉树
    题目链接226.翻转二叉树思路将左右子树抽象为两个结点,直接进行交换。然后再递归左右子树。代码classSolution{publicTreeNodeinvertTree(TreeNoderoot){......
  • 【Java】try...catch...finally执行顺序
    结论:如果try中没有异常,则顺序为try→finally;如果try中有异常,顺序为try→catch→finally,并且异常之后的代码不会执行。当try或catch中带有return时,会先执行return前的代......
  • 顺序结构
    顺序结构Java的基本结构就是顺序结构,除非特别指明,否则就按照顺序一条一条执行。顺序结构是最简单的算法结构语句与语句之间,框与框之间是按从上到下的顺序进行的,它是由若......