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;
}