回溯算法

• 要 8*8的棋盘上摆放8个“皇后”，要求“皇后”之间不能发生冲突，即任何两个“皇后”不能在同一行、同一列和相同的对角线上，则一般采用 （62） 来实现。（2011年上半年）

  （62） A. 分治法 B. 动态规划法 C. 贪心法 D. 回溯法

非递归求解把皇后

#include <math.h>
#include <stdio.h>
#define N 10
int q[N + 1]; // 存储皇后的列号
int check(int j) { // 检查第 j 个皇后的位置是否合法
    int i;
    for (i = 1; i < j; i ++ ) {
        if (q[i] == q[j] || abs(i - j) == abs(q[i] - q[j])) { // 判断是否在同一列和同一斜线上
            return 0;
        }
    }
    return 1;
}
void queen() { // 求解 N 皇后 方案
    int i;
    for (i = 1; i <= N; i ++ ) {
        q[i] = 0;
    }
    int answer = 0; // 方案数
    int j = 1; // 表示正在摆放第 j 个皇后
    while (j >= 1) {
        q[j] = q[j] + 1; // 让第 j 个皇后向后一列摆放
        while (q[j] <= N && !check(j)) { // 判断第 j 个皇后的位置是否合法
            q[j] = q[j] + 1; // 不合法就往后一个位置摆放
        }
        if (q[j] <= N) { // 表示第 j 个皇后的找到一个合法的摆放位置
            if (j == N) { // 找到了 N 皇后的一组解
                answer = answer + 1;
                printf("方案%d：", answer);
                for (i = 1; i <= N; i ++ ) {
                    printf("%d ", q[i]);
                }
                printf("\n");
            } else {
                j = j + 1; // 继续摆放下一个皇后
            }
        } else { // 表示第 j 个皇后找不到一个合法的摆放位置
            q[j] = 0; // 还原第 j 个皇后的位置
            j = j - 1; // 回溯
        }
    }
}
int main() {
    queen();
    return 0;
}

递归求解八皇后

#include <math.h>
#include <stdio.h>
#define N 10
int answer = 0;
int q[N + 1]; // 存储皇后的列号
int check(int j) { // 检查第 j 个皇后的位置是否合法
    int i;
    for (i = 1; i < j; i ++ ) {
        if (q[i] == q[j] || abs(i - j) == abs(q[i] - q[j])) { // 判断是否在同一列和同一斜线上
            return 0;
        }
    }
    return 1;
}
void queen(int j) {
    int i;
    for (i = 1; i <= N; i ++ ) {
        q[j] = i;
        if (check(j)) { // 当摆放的皇后位置为合法时
            if (j == N) { // 找到了 N 皇后的一组解
                answer = answer + 1;
                printf("方案%d：", answer);
                for (i = 1; i <= N; i ++ ) {
                    printf("%d ", q[i]);
                }
                printf("\n");
            } else {
                queen(j + 1); // 递归摆放下一个皇后的位置
            }
        }
    }
}
int main() {
    queen(1);
    return 0;
}

分治算法

• 二分查找
  
• 段 ： for（for（二分）） O lgn

//归并排序
#include <stdio.h>
#include <sched.h>
void Merge(int A[], int p, int q, int r) {
    int i, j, k;
    int L[50], R[50];
    int n1 = q - p + 1, n2 = r - q;
    for (i = 0; i < n1; i ++ ) {
        L[i] = A[p + i];
    }
    for (j = 0; j < n2; j ++ ) {
        R[j] = A[q + j + 1];
    }
    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    i = 0;
    j = 0;
    for (k = p; k < r + 1; k ++ ) {
        if (L[i] < R[j]) {
            A[k] = L[i];
            i ++ ;
        } else {
            A[k] = R[j];
            j ++ ;
        }
    }
}
void MergeSort(int A[], int p, int r) {
    int q;
    if (p < r) {
        q = (p + r) / 2;
        MergeSort(A, p, q);
        MergeSort(A, q + 1, r);
        Merge(A, p, q, r);
    }
}
int main() {
    int A[] = {4, 1, 3, 6, 8, 5, 2, 9};
    MergeSort(A, 0, 7);
    int i;
    for (i = 0; i < 8; i ++ ) {
        printf("%d ", A[i]);
    }
    return 0;
}

动态规划

// 01背包
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];//v:体积  w：价值
int f[N];//集合表示 一开始全为0

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        cin >> v[i] >> w[i];
    }
    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= v[i]; j --) { //可以选时才会更新状态
          f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    } 
    cout << f[m] << endl;
    return 0;
}

习题

贪心算法

//部分背包问题   删去一些代码  只展示伪代码部分
#include <stdio.h>
#define N 5 // 物品数量
#define W 10 // 背包容量
int v_temp[N + 1], w_temp[N + 1]; // 物品价值数组 和 物品重量数组的临时数组
double vw_temp[N + 1]; // 物品单位重量价值数组的临时数组
double answer[N + 1]; // 解方案数组
// 归并排序
void merge_sort(int v[], int w[], double vw[], int l, int r) {
		... // 按照 物品单位重量价值数组 从大到小的顺序排序
}
// 求解部分背包问题最优解
double Max_Value(int v[], int w[], double vw[]) {
    double result = 0.0;
    int i;
    int W_temp = W;
    for (i = 1; i <= N; i ++ ) {
        if (W_temp >= w[i]) { 
// 当前背包容量 大于等于 物品重量 就直接全部装入到背包中   
            answer[i] = 1.0;
            result = result + v[i];
            W_temp = W_temp - w[i];
        } else { // 当前背包容量 小于 物品重量 就应该将该物品的一部分装入到背包中
            break;
        }
    }
    if (W_temp > 0 && i <= N) { // 当前背包还有剩余容量 并且 还有可选的物品
        answer[i] = (double) W_temp / w[i];
        result = result + W_temp * vw[i];
    }
    return result;
}
int main() {
    int v[] = {0, 6, 3, 5, 4, 6}; // 物品价值数组
    int w[] = {0, 2, 2, 6, 5, 4}; // 物品重量数组
    for (i = 1; i <= N; i ++ ) vw[i] = (double) v[i] / w[i];
    merge_sort(v, w, vw, 1, N);
    
    double result = Max_Value(v, w, vw); // 求解
    return 0;
}

习题

算法总和

• 回溯法 : 深度优先DFS 的策略
• 分支界限法 ： 广度优先BFS 的策略
  

习题