算法笔记——搜索篇

深度优先搜索（DFS）

背包问题

有 n 件物品，每件物品的重量为 w[i], 价值为 c[i]。现在需要选出若干件物品放入一个容量为 V 的背包中，使得在选入背包的物品重量和不超过容量 V 的前提下，让背包中物品的价值之和最大，求最大价值。（1<= n <= 20）

输入数据：

5 8 //5 件物品，背包容量为 8
3 5 1 2 2 //重量分别为 3 5 1 2 2
4 5 2 1 3 //价值分别为 4 5 2 1 3

输出数据：

10

实现代码：

# include <cstido>
const int maxn = 30;
int n, V, maxValue = 0; //物品件数 n，背包容量 V，最大价值 maxValue
int w[maxn], c[maxn]; //w[i] 为每件物品的重量，c[i] 为每件物品的价值
// DFS, index 为当前处理的物品编号
// sumW 和 sumC 分别为当前总重量和当前总价值
void DFS(int index, int sumW, int sumC){
    if(index == n){ //已经完成对 n 件物品的选择（死胡同）
        if(sumW <= V && sumC > maxValue){
            maxValue = sumC; //不超过背包容量时更新最大价值 maxValue
        }
        return;
    }
    //岔道口
    DFS(index + 1, sumW, sumC); //不选第 index 件物品
    DFS(index + 1, sumW + w[index], sumC + c[index]); //选第 index 件物品
}
int main(){
    scanf("%d%d", &n, &V);
    for(int i = 0; i < n; i++){
        scanf("%d", &w[i]); //每件物品的重量
    }
    for(int i = 0; i < n; i++){
        scanf("%d", &c[i]); //每件物品的价值
    }
    DFS(0, 0, 0); //初始时为第 0 件物品、当前总重量和总价值均为 0
    printf("%d\n", maxValue);
    return 0;
}

广度优先搜索（BFS）

给出一个 m * n 的矩阵，矩阵中的元素为 0 或 1。称位置 (x, y) 与其上下左右四个位置 (x, y + 1)、(x, y - 1)、(x + 1, y)、(x - 1, y) 是相邻的。如果矩阵中有若干个 1 是相邻的（不必两两相邻），那么称这些 1 构成了一个 “块”。求给定的矩阵中 “块” 的个数。

0 1 1 1 0 0 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0

上面的 6 * 7 的矩阵中，“块”的个数为 4。

实现代码：

# include <cstido>
# include <queue>
using namespace std;
const int maxn = 100;
struct node{
    int x, y;
} Node;

int n, m;
int matrix[maxn][maxn];
bool inq[maxn][maxn] = {false};
int X[4] = {0, 0, 1, -1};
int Y[4] = {1, -1, 0, 0};

bool judge(int x, int y){
    if(x >= n || x < 0 || y >= m || y < 0) return false;
    //
    if(matrix[x][y] == 0 || inq[x][y] == true) return false;
    //
    return true;
}
//
void BFS(int x, int y){
    queue<node> Q;
    Node.x = x, Node.y = y;
    Q.push(Node); //将结点 Node 入队
    inq[x][y] = true; //设置(x, y) 已入过队
    while(!Q.empty()){
        node top = Q.front(); //取出队首元素
        Q.pop(); //队首元素出队
        for(int i = 0; i < 4; i++){ //循环 4 次，得到 4 个相邻位置
            int newX = top.x + X[i];
            int newY = top.y + Y[i];
            if(judge(newX, newY)){ //如果新位置 (newX, newY) 需要访问
                //设置 Node 的坐标为 (newX, newY)
                Node.x = newX, Node.y = newY;
                Q.push(Node); //将结点 Node 加入队列
                inq[newX][newY] = true; //设置位置 (newX, newY) 已入过队
            }
        }
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for(int x = 0; x < n; x++){
        for(int y = 0; y < m; y++){
            scanf("%d", &matrix[x][y]); //读入 01 矩阵
        }
    }
    int ans = 0; //存放块数
    for(int x = 0; x < n; x++){ //枚举每一个位置
        for(int y = 0; y < m; y++){
            if(matrix[x][y] == 1 && inq[x][y] == false){
                ans++; //块数加 1
                BFS(x, y); //访问整个块，将该块所有 "1" 的 inq 都标记为 true
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}