一些经典的算法核心代码

算法课时课下作业，做此总结。极个别可能有小错误。

文章目录

• 一些经典的算法核心代码
• • 一、递归与分治
  • • 01. 斐波那契、汉诺塔、全排列
    • • Fibonacci
      • 汉诺塔
      • 全排列
    • 02. 棋盘覆盖、六种排序
    • • 棋盘覆盖
      • 冒泡排序
      • 选择排序
      • 插入排序
      • 快速排序
      • 归并排序
      • 堆排序
    • 03. 最接近点对问题
    • • 最接近点对问题
  • 二、动态规划
  • • 04. 币值最大化、矩阵连乘
    • • 币值最大化
      • 矩阵连乘
    • 05. 最长公共子序列、流水作业调度
    • • 最长公共子序列
      • 流水作业调度-Johnson算法（非动态规划算法）
    • 06. 0-1背包 最优二叉搜索树
    • • 0-1背包
      • 最优二叉搜索树
• 三、贪心算法
• • • 07. 活动安排、背包问题
    • • 活动安排
      • 背包问题
    • 08. 哈夫曼编码
    • 09. 单源最短路径 最小生成树
    • • 单源最短路径-Dijkstra算法
      • 最小生成树-Prim算法
      • 最小生成树-Kruskal算法
• 四、回溯法
• • • 10. 子集树、装载问题
    • • 子集树
      • 装载问题
    • 11. 子集和问题、n后问题
    • • 子集和问题
      • n后问题
    • 12. 单源最短路径、着色问题、旅行售货员
    • • 单源最短路径
      • 着色问题
      • 旅行售货员

一、递归与分治

01. 斐波那契、汉诺塔、全排列

Fibonacci

#include <iostream>
#include <stdio.h>
#define max 10005
using namespace std;

//递归
int Recursion(int n)
{
    if(n<=2) return 1;
    return Recursion(n-1)+Recursion(n-2);
}

//简单循环，无数组
int Loop(int n)
{
    int f,b,temp;
    f=0;
    b=1;
    if(n<=1) return 1;
    for(int i=1;i<n;i++)
    {
        printf("%d ",b);
        temp=f+b;
        f=b;
        b=temp;
    }
    //打印输出
    printf("%d",b);
}

//数组
int Array(int n)
{
    int a[max];
    a[0]=0;a[1]=1;
    if(n>1)
    {
        for(int i=2;i<=n;i++) a[i]=a[i-1]+a[i-2];
    }
    //打印输出
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
}

int main()
{
    int n;
    printf("计算到几项：");
    scanf("%d",&n);

    printf("递归实现：");
    printf("第%d项为：%d",n,Recursion(n));

    printf("\n循环实现：");
    Loop(n);

    printf("\n数组实现：");
    Array(n);

    return 0;
}

汉诺塔

#include <iostream>
#include <stdio.h>

using namespace std;

int coun=0;
void hanoi(int n,char A,char B,char C)
{
    if (n>0)
    {
        hanoi(n-1,A,C,B);
        coun++;
        printf("第%d次移动：把%c的盘子移动到%c\n",coun,A,C);
        hanoi(n-1,B,A,C);
    }
}

int main()
{
    int n;
    cout<<"请输入盘子的个数：";
    cin>>n;
    hanoi(n,'A','B','C');
    return 0;
}

全排列

#include <iostream>

using namespace std;
int j;//递归过程中需要k不变，用j代替最后用循环输出 

void Permutation(int *num,int k,int m)
{
    int temp;
    if(k==m)//只剩一个元素
    {
        for(int i=j;i<=m;i++)
        {
            cout<<num[i];
        }
        cout<<"   ";
    }
    else//还有多个元素
    {
        for(int i=k;i<=m;i++)
        {
            temp=num[k];num[k]=num[i];num[i]=temp;
            Permutation(num,k+1,m);
            temp=num[k];num[k]=num[i];num[i]=temp;//再交换回来恢复原位
        }
    }
}

int main()
{
    int num[10]= {0,1,2,3,4,5,6,7,8,9};
    int k,m;
    cout <<"产生从k到m的全排列:" <<endl;
    cout <<"k:"; cin>>k;
    cout <<"m:"; cin>>m;
    j=k;
    Permutation(num,k,m);
    cout<<""<<endl;
    return 0;
}

02. 棋盘覆盖、六种排序

棋盘覆盖

int board[maxnum][maxnum];
int tile=1;

void ChessBoard(int tr,int tc,int dr,int dc,int ssize)
{
    if(ssize==1) return;
    int t=tile++;//l型骨牌号
    int s=ssize/2;//分割棋盘

    //覆盖左上角子棋盘
    if(dr<tr+s && dc<tc+s)//特殊方格在此棋盘
        ChessBoard(tr,tc,dr,dc,s);
    else{//此棋盘无特殊方格
        //用t号L型骨盘覆盖右下角
        board[tr+s-1][tc+s-1]=t;
        //覆盖其余方格
        ChessBoard(tr,tc,tr+s-1,tc+s-1,s);
    }

    //覆盖右上角子棋盘
    if(dr<tr+s&&dc>=tc+s)//特殊方格在此棋盘
        ChessBoard(tr,tc+s,dr,dc,s);
    else{//此棋盘无特殊方格
        //用t号L型骨盘覆盖左下角
        board[tr+s-1][tc+s]=t;
        //覆盖其余方格
        ChessBoard(tr,tc+s,tr+s-1,tc+s,s);
    }

    //覆盖左下角子棋盘
    if(dr>=tr+s && dc<tc+s)//特殊方格在此棋盘
        ChessBoard(tr+s,tc,dr,dc,s);
    else{//此棋盘无特殊方格
        //用t号L型骨盘覆盖右上角
        board[tr+s][tc+s-1]=t;
        //覆盖其余方格
        ChessBoard(tr+s,tc,tr+s,tc+s-1,s);
    }

    //覆盖右夏角子棋盘
    if(dr>=tr+s && dc>=tc+s)//特殊方格在此棋盘
        ChessBoard(tr+s,tc+s,dr,dc,s);
    else{//此棋盘无特殊方格
        //用t号L型骨盘覆盖左上角
        board[tr+s][tc+s]=t;
        //覆盖其余方格
        ChessBoard(tr+s,tc+s,tr+s,tc+s,s);
    }
}

int main()
{
    int x,y,ssize;//x，y是特殊方格的坐标，没有0行0列
    cin>>x>>y>>ssize;
    memset(board,0,sizeof(board));
    ChessBoard(0,0,x-1,y-1,ssize);
    for(int i=0;i<ssize;i++){
        for(int j=0;j<ssize;j++)
            printf("%4d",board[i][j]);
        cout << endl;
    }
    return 0;
}

冒泡排序

对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
2. 对每一个相邻元素做同样的工作，从开始第一对到结尾的每一对。在这一 点，最后的元素应该会是最大的数。
3. 针对多有的元素重复以上的步骤，除了最后一个。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#define num 10005
using namespace std;

//打印
void Display(int *a, int length)
{
    for (int i=0; i<length; i++)
    {
        printf("%-4d",a[i]);
    }
    printf("\n");
}

// 冒泡排序
void BubbleSort(int *a, int length)
{
    for (int i=0; i<length-1; ++i)
    {
        int flag=0;
        for (int j=0; j<length-1-i; ++j)
        {
            if (a[j]>a[j+1])
            {
                swap(a[j], a[j+1]);
                flag=1;
            }
        }
        if (flag==0) break;
    }
}

int main()
{
    int a[num];
    int length;
    printf("冒泡排序\n");
    printf("请输入需要排序的数字个数：");
    cin>>length;
    printf("请输入需要排序的数字：");
    for(int i=0; i<length; i++)
    {
        scanf("%d",&a[i]);
    }
    BubbleSort(a,length);
    printf("排序后的结果为：");
    Display(a,length);
    return 0;
}

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

//选择排序
void SelectSort(int *a, int length)
{
    for (int i=0; i<length-1; ++i)
    {
        int min=i;
        for (int j=i+1; j<length; ++j)
        {
            if (a[j]<a[min])
            {
                min=j;
            }
        }
        swap(a[i], a[min]);
    }
}

插入排序

将待排序的无序数列看成是一个仅含有一个元素的有序数列和一个无序数列，将无序数列中的元素逐次插入到有序数列中，从而获得最终的有序数列。

//插入排序
void InsertSort(int *a, int length)
{
    for (int i=1; i<length; ++i)
    {
        int tmp=a[i];
        int j=0;
        for (j=i-1; j>=0; --j)
        {
            if (a[j]>tmp)
            {
                a[j + 1]=a[j];
            }
            else
                break;

        }
        a[j+1] = tmp;
    }
}

快速排序

快速排序是找出一个元素（理论上可以随便找一个）作为基准，然后对数组进行分区操作，使基准左边元素的值都不大于基准值，基准右边的值都不小于基准值，如此作为基准的元素调整到排序后的正确位置。

void QuickSort(int *a,int left,int right)
{
    int i, j, t, temp;
    if(left > right)
        return;
    temp = a[left];
    i = left;
    j = right;
    while(i != j)
    {
        while(a[j] >= temp && i < j)
            j--;
        while(a[i] <= temp && i < j)
            i++;
        if(i < j)
        {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    a[left] = a[i];
    a[i] = temp;
    QuickSort(a,left, i-1);
    QuickSort(a,i+1, right);
}

int main()
{
    QuickSort(a,0,length-1);
    return 0;
}

归并排序

归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，合并成一个大的分组，逐层进行，最终所有的元素都是有序的

//归并排序
void Merge(int* a,int left,int mid,int right)
{
    int *temp = new int[right-left+1];
    int st1=left;  //数组1
    int st2=mid + 1; //数组2
    int t=0; //合并数组的
    while (st1<=mid && st2<=right)
    {
        temp[t++]=a[st1]<a[st2]?a[st1++]:a[st2++];
    }
    while (st1<=mid)
    {
        temp[t++]=a[st1++];
    }
    while (st2<=right)
    {
        temp[t++]=a[st2++];
    }
    for (int j=0;j<t;++j)
    {
        a[left+j]=temp[j];
    }
    delete[] temp; //销毁临时变量
}

void MergeSort(int* a,int start, int end)
{
    if (a==NULL ||start>=end)
        return;
    if (start<end)
    {
        int mid=(start+end) / 2; //分块的中间值

        MergeSort(a,start,mid);  //左边递归进行分离和合并
        MergeSort(a,mid+1,end);  //右边递归进行分离和合并
        Merge(a,start,mid,end); //左右合并
    }
}

int main()
{
    MergeSort(a,0,length-1);
}

堆排序

//从小到大排序，最后一次得到最终结果
void Down(int a[],int i,int n)
{
    int parent=i;
    int child=2*i+1;
    while (child<n)
    {
        if (child+1<n&&a[child]<a[child+1])
        {
            child++;
        }
        if (a[parent]<a[child]) //父节点小于子节点,交换父节点和子节点
        {
            swap(a[parent], a[child]);
            parent=child;
        }
        child=child*2+1;
    }
}

//初始化堆
void BuildHeap(int a[],int length)
{
    for (int i=length/2-1;i>=0;i--)
    {
        Down(a,i,length);
    }
}

//堆排序
void HeapSort(int a[],int length)
{
    BuildHeap(a, length);
    for (int i = length - 1; i > 0; i--)
    {
        swap(a[0],a[i]);  // 交换顶点和第 i 个数据
        Down(a,0,i); // 重新建立大顶堆
    }
}

• 总结

03. 最接近点对问题

最接近点对问题

1.一维

public class ClosestPari.java {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("请输入坐标个数");
        int len = sc.nextInt();
        double[] s = new double[len];
        for (int i = 0; i < len; i++) {
            System.out.print("请输入第" + (i + 1) + "坐标:");
            s[i] = sc.nextDouble();
        }
        System.out.println("最接近点对距离是：" + cpair1(s));
    }

    public static double cpair1(double[] s) {
        int n = s.length;
        if (n < 2)
            return Double.MAX_VALUE;
        double m = mid(s);
        int right = 0;
        for (int i = 0; i < s.length; i++) {
            if (s[i] > m) {
                right = i;
                break;
            }
        }
        double[] s1 = child(s, 0, right);
        double[] s2 = child(s, right, n);
        double d1 = cpair1(s1);
        double d2 = cpair1(s2);

        double d = 0;
        if(s1.length==0||s2.length==0)
            d = Math.min(d1, d2);
        else{
            double p = max(s1);
            double q = min(s2);
            d = min(d1, d2, q - p);
        }
        return d;
    }

    /**
     * 求原数组在下标 [left-right]之间的子数组
     * @param s
     * @param left  子数首元素在原数组中组起始下标
     * @param right 子数末尾元素在原数组中最后下标
     * @return 返回原数组在下标 [left-right) 之间的子数组
     */
    private static double[] child(double[] s, int left, int right) {
        int len = right - left;
        double[] c = new double[len];
        for (int i = left, j = 0; i < right; i++, j++) {
            c[j] = s[i];
        }
        return c;
    }

    /**
     * 求S中点的坐标的中位数
     * @param s
     * @return 返回中位数
     */
    private static double mid(double[] s) {
        Arrays.sort(s);
        if (s.length % 2 == 1) {
            return s[s.length / 2];
        } else {
            return (s[s.length / 2] + s[s.length / 2 - 1]) / 2;
        }
    }

    /**
     * 返回数组中最大值
     * @param s 数组
     * @return
     */
    private static double max(double[] s) {
        return s[s.length - 1];
    }

    /**
     * 返回三个数中最小的一个
     * @param s
     * @return
     */
    private static double min(double[] s) {
        return s[0];
    }
    /**
     * 返回三个数中最小的
     * @param a
     * @param b
     * @param c
     * @return
     */
    private static double min(double a, double b, double c) {
        return (a < b ? (a < c ? a : c) : b < c ? b : c);
    }
}

2.二维

package homework3;

import java.util.Scanner;

public class ClosestPari {
    static int[] close = new int[2];
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.print("要输入点的个数");
        int n = s.nextInt();
        Point1[] x = new Point1[n];
        Point1[] xx = new Point1[n];


        for (int i = 0; i < n; i++) {
            System.out.print("请输入第" + (i+1) +"个点的横纵坐标（以空格间隔）：");
            x[i] = new Point1(s.nextDouble(), s.nextDouble(), i+1);
            xx[i] = x[i];//保存初始点数组
        }

        double closest = cpair2(x).dist;
        System.out.println("对接近点对的坐标是:(" + xx[close[0]-1].x +"," + xx[close[0]-1].y + ")  ("
                + xx[close[1]-1].x +"," + xx[close[1]-1].y+ ")\n距离是:" + closest);
    }

    public static Pair cpair2(Point1[] x){
        if(x.length < 2)
            return null;
        //依照x坐标排序
        MergeSort.mergeSort(x);

        Point2[] y = new Point2[x.length];

        for(int i = 0; i < x.length; i++)
        {
            //将数组x中的点复制到数组y中
            y[i] = new Point2(x[i].x, x[i].y, i);
        }
        //依照y坐标排序
        MergeSort.mergeSort(y);

        Point2[] z = new Point2[x.length];

        //计算最接近点对
        return closestPair(x, y, z,0, x.length-1);
    }

    private static Pair closestPair(Point1[] x, Point2[] y, Point2[] z, int left, int right) {
        if(right - left == 1)//2点情形
            return new Pair(x[left], x[right], dist(x[left], x[right]));
        if(right - left == 2)
        {
            double d1 = dist(x[left], x[left+1]);
            double d2 = dist(x[left+1], x[right]);
            double d3 = dist(x[left], x[right]);

            if(d1 <= d2 && d1 <= d3)
                return new Pair(x[left], x[left+1], d1);
            if(d2 <= d3)
                return new Pair(x[left+1], x[right], d2);
            else
                return new Pair(x[left], x[right], d3);
        }

        int m = (left + right) / 2;
        int f = left, g = m + 1;
        for (int i = left; i <= right; i++) {
            if(y[i].p > m)
                z[g++] = y[i];
            else
                z[f++] = y[i];
        }

        Pair best = closestPair(x, z, y, left, m);
        Pair pr = closestPair(x, z, y, m + 1, right);

        if(pr.dist < best.dist)
            best = pr;

        //重构数组
        MergeSort.mergeSort(z, y, left, m, right);

        //d矩形条内的点置于z中
        int k = left;
        for (int i = left; i <= right; i++) {
            if(Math.abs(x[m].x - y[i].x) < best.dist)
                z[k++] = y[i];
        }
        //搜索z[left: k-1]
        for (int i = left; i < k; i++) {
            for (int j = i + 1; j < k && z[j].y - z[i].y < best.dist; j++) {
                double dp = dist(z[i], z[j]);
                if(dp < best.dist)
                    best = new Pair(x[z[i].p], x[z[j].p], dp);
                System.out.println(x[z[i].p].id);
                System.out.println(x[z[j].p].id);

                close[0] = x[z[i].p].id;
                close[1] = x[z[j].p].id;
            }
        }
        return best;
    }

    //平面上任意两点间距离
    public static double dist(Point u, Point v){
        double dx = u.x - v.x;
        double dy = u.y - v.y;
        return Math.sqrt(dx * dx + dy * dy);
    }

    public static class Point {
        double x, y; //坐标

        Point() {
        }

        public Point(double xx, double yy) {
            x = xx;
            y = yy;
        }
    }

    public static class Point1 extends Point implements Comparable {
        int id; // 点编号
        public Point1(double xx, double yy, int theID) {
            super(xx, yy);
            id = theID;
        }

        @Override
        public int compareTo(Object o) {
            double xx = ((Point1) o).x;
            if (this.x < xx)
                return -1;
            if (this.x == xx)
                return 0;
            return 1;
        }

        @Override
        public boolean equals(Object o) {
            return this.x == ((Point1) o).x;
        }
    }

    public static class Point2 extends Point implements Comparable {
        int p; // 同一点在数组x中的坐标

        public Point2(double xx, double yy, int pp) {
            super(xx, yy);
            p = pp;
        }

        @Override
        public int compareTo(Object o) {
            double xy = ((Point2) o).y;
            if (this.y < xy)
                return -1;
            if (this.y == xy)
                return 0;
            return 1;
        }

        @Override
        public boolean equals(Object o) {
            return this.y == ((Point2) o).y;
        }
    }

    public static class Pair{
        Point1 a;//平面点a
        Point1 b;//平面点b
        double dist;

        public Pair(Point1 aa, Point1 bb, double dd){
            a = aa;
            b = bb;
            dist = dd;
        }
    }
}

二、动态规划

04. 币值最大化、矩阵连乘

币值最大化

public class MaxMoney {

    static int[] a = null;
    static int[] c = null;
    static int[] f = null;
    static int[] arr = null;
    
    private static void initArray(int n) {
        a = new int[n+1];
        c = new int[n+1];
        f = new int[n+1];
        arr = new int[n+1];
    }

    //普通递归求
    static int fun1(int n) {
        if (n == 0)
            return c[0];
        if (n == 1)
            return Math.max(c[0], c[1]);
        else
            return Math.max(c[n] + fun1(n - 2), fun1(n - 1));
    }

    //备忘录
    static int fun2(int n) {
        if (n == 0)
            return c[0];
        if (n == 1)
            return Math.max(c[0], c[1]);
        else if (a[n] != 0)
            return a[n];
        return a[n] = Math.max(c[n] + fun2(n - 2), fun2(n - 1));
    }

    //动态规划法求
    static void coinRow(int n) {
        f[0] = 0;
        f[1] = c[1];

        for (int i = 2; i <= n; i++) {
            f[i] = Math.max(c[i] + f[i-2], f[i-1]);
        }
    }
    
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.print("请输入硬币的个数:");
        int n = s.nextInt();

        initArray(n);
        System.out.println("输每个硬币面额:");
        for (int i = 1; i <= n; i++) {
            c[i] = s.nextInt();
        }

        System.out.print("递归法求得结果为：" + fun1(n));

        System.out.print("\n备忘录法求得结果为：" + fun2(n ));

        System.out.print("\n动态规划法求得结果为：");
        coinRow(n);
        System.out.println(f[n]);

        int count = 0;
        for (int i = n; i >= 1 ; i--) {
            if (f[i] == f[i - 1])
            {
                arr[count++] = c[--i];
            } else {
                arr[count++] = c[i--];
            }
        }
        System.out.println("拿的面额分别为");
        for (int i = n; i >= 0; i--) {
            if(arr[i] > 0)
                System.out.print(arr[i] + "\t");
        }
    }
}

矩阵连乘

public class MatrixMultiplication {
    static int[][] s1 = null;
    static int[][] s2 = null;
    static int[][] s3 = null;
    static int[][] m1 = null;
    static int[][] m2 = null;

    public static void main(String[] args) {
        //快速测试样例
        int[] p = new int[]{30, 35, 15, 5, 10, 20, 25, 50, 24, 36, 48, 50, 25, 19, 27, 74, 89};//矩阵维数
        int n = p.length-1;//矩阵个数
        //初始化数组
        initArray(n);

        matrixChain(p, m1);
        System.out.println("\n==============================不同划分的计算次数为:==============================");
        for (int i = 1; i <= n; i++) {
            for (int j = 2; j <= n; j++) {
                System.out.printf("%10d\t", m1[i][j]);
            }
            System.out.println();
        }

        fun("动态规划法", 1, n, p);
        fun("备忘录法", 2, n, p);
        fun("递归法", 3, n, p);
    }

    private static void initArray(int n) {
        s1 = new int[n+1][n+1];
        s2 = new int[n+1][n+1];
        s3 = new int[n+1][n+1];
        m1 = new int[n+1][n+1];
        m2 = new int[n+1][n+1];
    }

    private static void matrixChain(int[] p, int[][] m) {
        int n = p.length - 1;
        for (int i = 1; i <= n; i++) {
            m[i][i] = 0;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= n - i + 1; j++) {
                int k = j + i - 1;
                m[j][k] = m[j + 1][k] + p[j - 1] * p[j] * p[k];
                s1[j][k] = j;
                for (int q = j + 1; q < k; q++) {
                    int t = m[j][q] + m[q + 1][k] + p[j - 1] * p[q] * p[k];
                    if (t < m[j][k]) {
                        m[j][k] = t;
                        s1[j][k] = q;
                    }
                }
            }
        }
    }

    private static int lookupChain(int i, int j, int[] p) {
        if (m2[i][j] > 0)
            return m2[i][j];
        if (i == j)
            return 0;
        int u = lookupChain(i + 1, j, p) + p[i - 1] * p[i] * p[j];
        s2[i][j] = i;
        for (int k = i + 1; k < j; k++) {
            int t = lookupChain(i, k, p) + lookupChain(k + 1, j, p) + p[i - 1] * p[k] * p[j];
            if (t < u) {
                u = t;
                s2[i][j] = k;
            }
        }
        m2[i][j] = u;          //纪录最小次数
        return u;
    }

    private static int RecurMatrixChain1(int i, int j, int p[]) {
        if (i == j) return 0;
        int u = RecurMatrixChain1(i, i, p) + RecurMatrixChain1(i + 1, j, p) + p[i - 1] * p[i] * p[j];
        s3[i][j] = i;
        for (int k = i + 1; k < j; k++) {
            int t = RecurMatrixChain1(i, k, p) + RecurMatrixChain1(k + 1, j, p) + p[i - 1] * p[k] * p[j];
            if (t < u) {
                u = t;
                s3[i][j] = k;
            }
        }
        return u;
    }

    private static void traceback(int[][] s, int i, int j) {
        if (j == 0)
            return;
        if (i == j)
            System.out.print("A" + i);
        else {
            System.out.print("(");
            traceback(s, i, s[i][j]);
            traceback(s, s[i][j] + 1, j);
            System.out.print(")");
        }
    }

    static void  fun(String method, int which, int n, int[] p){
        System.out.println("=================================" + method + "=================================");
        System.out.print(method + "求解出最少计算次数为：");
        Date date1 = new Date();
        switch (which){
            case 1:
                matrixChain(p, m1);
                System.out.print(m1[1][n] + "\n矩阵划分为：");
                traceback(s1, 0, n);
                break;
            case 2:
                System.out.println(lookupChain(1, n, p));
                System.out.print("矩阵划分为：");
                traceback(s2, 0, n);
                break;
            case 3:
                System.out.println(RecurMatrixChain1(1, n, p));
                System.out.print("矩阵划分为：");
                traceback(s3, 0, n);
                break;
        }
        Date date2 = new Date();

        System.out.println("\n耗费时间为：" + (date2.getTime()-date1.getTime()) + "毫秒");
    }
}

05. 最长公共子序列、流水作业调度

最长公共子序列

public class LongestCommonSubsequence {

    //递归
    public static int recLCS(char[] x, char[] y, int i, int j) {
        if (i > 0 && j > 0) {
            if (x[i] != y[j]) {
                return max((recLCS(x, y, i, j - 1)), (recLCS(x, y, i - 1, j)));
            } else {
                return (recLCS(x, y, i - 1, j - 1)) + 1;
            }
        }
        return 0;
    }

    //备忘录
    public static int noteLCS(char[] x, char[] y, int i, int j, int[][] c) {
        if (c[i][j] > -1) {
            return c[i][j];
        }
        if (i == 0 || j == 0) {
            c[i][j] = 0;
        } else if (x[i] == y[j]) {
            c[i][j] = noteLCS(x, y, i - 1, j - 1, c) + 1;
        } else {
            c[i][j] = max(noteLCS(x, y, i, j - 1, c), noteLCS(x, y, i - 1, j, c));
        }
        return c[i][j];
    }

    //动态规划
    public static int lcsLength(int m, int n, char[] x, char[] y, int[][] b) {
        int[][] c = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            c[i][0] = 0;
        }
        for (int i = 0; i <= n; i++) {
            c[0][i] = 0;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (x[i] == y[j]) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                    b[i][j] = 1;
                } else if (c[i - 1][j] >= c[i][j - 1]) {
                    c[i][j] = c[i - 1][j];
                    b[i][j] = 2;
                } else {
                    c[i][j] = c[i][j - 1];
                    b[i][j] = 3;
                }
            }
        }
        return c[m][n];
    }

    //最长公共子序列输出
    public static void lcs(int i, int j, char[] x, int[][] b) {
        if (i == 0 || j == 0) {
            return;
        }
        if (b[i][j] == 1) {
            lcs(i - 1, j - 1, x, b);
            System.out.print(x[i]);
        } else if (b[i][j] == 2) {
            lcs(i - 1, j, x, b);
        } else {
            lcs(i, j - 1, x, b);
        }
    }

    public static void main(String[] args) {
        char[] x = {'0', 'A', 'B', 'C', 'B', 'D', 'A', 'B'};
        char[] y = {'0', 'B', 'D', 'C', 'A', 'B', 'A'};
        int m = x.length - 1;
        int n = y.length - 1;
        int[][] b = new int[m + 1][n + 1];

        System.out.println("递归方法得到子序列长度为：" + recLCS(x, y, m, n));

        int[][] c = new int[m + 1][n + 1];
        for (int q = 0; q <= m; q++) {
            for (int p = 0; p <= n; p++) {
                c[q][p] = -1;//备忘录先初始化为-1
            }
        }
        noteLCS(x, y, m, n, c);
        System.out.println("备忘录方法得到子序列长度为：" + c[m][n]);

        System.out.println("动态规划方法得到子序列长度为：" + lcsLength(m, n, x, y, b));
        System.out.print("子序列为：");
        lcs(m, n, x, b);
        System.out.println();
    }
}

流水作业调度-Johnson算法（非动态规划算法）

public class Johnson {

    //之前所做作业排序
    private static void mergesort(Comparable[] a) {
        Comparable[] b = new Comparable[a.length];
        int s = 1;
        while (s < a.length) {
            mergePass(a, b, s);//合并到数组b
            s += s;
            mergePass(b, a, s);//合并到数组a
            s += s;
        }
    }
    //合并大小为s的相邻子数组

    private static void mergePass(Comparable[] x, Comparable[] y, int s) {
        int i = 0;
        while (i <= x.length - 2 * s) {//合并大小为s的相邻2段子数组
            merge(x, y, i, i + s - 1, i + 2 * s - 1);
            i = i + 2 * s;
        }
        //剩下的元素个数少于2s
        if (i + s < x.length) {
            merge(x, y, i, i + s - 1, x.length - 1);
        } else {//复制到y
            for (int j = i; j < x.length; j++) {
                y[j] = x[j];
            }
        }
    }

    //合并 c[l:m]和c[m+1:r]到d[l:r]
    private static void merge(Comparable[] c, Comparable[] d, int l, int m, int r) {
        int i = l,
                j = m + 1,
                k = l;
        while ((i <= m) && (j <= r)) {
            if (c[i].compareTo(c[j]) <= 0) {
                d[k++] = c[i++];
            } else {
                d[k++] = c[j++];
            }
        }
        if (i > m) {
            for (int q = j; q <= r; q++) {
                d[k++] = c[q];
            }
        } else {
            for (int q = i; q <= m; q++) {
                d[k++] = c[q];
            }
        }
    }

    public int[] a;
    public int[] b;
    public int[] c;

    public Johnson(int[] aa, int[] bb) {
        this.a = aa;
        this.b = bb;
        this.c = new int[aa.length];
    }
    
    private static class Element implements Comparable {

        int key;
        int index;
        boolean job;

        private Element(int kk, int ii, boolean jj) {
            key = kk;
            index = ii;
            job = jj;
        }

        public int compareTo(Object x) {
            int xkey = ((Element) x).key;
            if (key < xkey) {
                return -1;
            }
            if (key == xkey) {
                return 0;
            }
            return 1;
        }
    }

    public static int flowShop(int a[], int b[], int c[]) {
        int n = a.length;
        Element d[] = new Element[n];
        for (int i = 0; i < n; i++) {
            int key = a[i] < b[i] ? a[i] : b[i]; //找在两台机器上处理时间小的那个时间
            boolean job = a[i] < b[i];
            d[i] = new Element(key, i, job);
        }
        mergesort(d);        //将所有作业的key进行从小到大排序
        int j = 0;
        int k = n - 1;                 //将作业按照Johnson法则排序放入c中
        for (int i = 0; i < n; i++) {
            if (d[i].job) {
                c[j++] = d[i].index;   //如果ai<bi,将其作业序号放入c数组中（从头开始放）
            } else {
                c[k--] = d[i].index; //否则 从数组未往前排
            }
        }
        j = a[c[0]];               //第一个作业在M1上的处理时间
        k = j + b[c[0]];              //第一个作业处理完所需时间
        for (int i = 1; i < n; i++) {
            j += a[c[i]];              //第i个作业在机器上加工完成所需时间
            k = j < k ? k + b[c[i]] : j + b[c[i]];/*如果此作业在M1上加工完成时间(包含前面作业在M1上的所用时间和)大于上一个作业完成时间，则此作业所需时间为k+b[c[i]]，否则为j+b[c[i]]*/
        }
        System.out.print("作业调度的顺序为：");
        int i;
		for(i=0;i<c.length-1;i++){
			System.out.print(c[i]+" -> ");
		}
                System.out.print(c[i]);
		System.out.println();
		return k;
    }

    public static void main(String[] args) {
        int[] a = {6, 4, 2, 2, 5};
        int[] b = {2, 6, 3, 1, 7};
        Johnson j = new Johnson(a, b);
        int k = j.flowShop(j.a, j.b, j.c);
        System.out.println("完成作业的最短时间为:" + k);
    }
}

06. 0-1背包 最优二叉搜索树

0-1背包

public class knapsack {

    //递归方法
    public static int recKnapsack(int n, int c, int[] w, int[] v) {
        int r = 0;
        if (n == -1) {
            return 0;
        }
        //如果剩余空间大于所放的物品
        if (c>= w[n]) {
            int r1 = recKnapsack(n - 1, c - w[n], w, v) + v[n]; //第n件放入背包
            int r2 = recKnapsack(n - 1, c, w, v);//不放第n件
            r = Math.max(r1, r2);
        }
        return r;
    }

    //动态规划方法
    //从m数组的最后一行填起，一行一行往上填，右上角为最终结果
    public static void knapsack(int v[], int w[], int c, int[][] m) {
        int n = v.length - 1;
        int jMax = min(w[n] - 1, c);//以下填最后一行，要么填0，要么填v[n]
        for (int j = 0; j <= jMax; j++) {
            m[n][j] = 0;
        }
        for (int j = w[n]; j <= c; j++) {
            m[n][j] = v[n];
        }

        for (int i = n - 1; i > 1; i--) {
            jMax = min(w[i] - 1, c);
            for (int j = 0; j <= jMax; j++)//背包剩余容量j<=jMax<c  
            {
                m[i][j] = m[i + 1][j];  //i没放，价值等于前
            }
            for (int j = w[i]; j <= c; j++) {
                m[i][j] = max(m[i + 1][j], (m[i + 1][j - w[i]] + v[i]));//效益值增长vi   
            }
        }
        m[1][c] = m[2][c];  //下面填第一行最后一列
        if (c >= w[1]) {
            m[1][c] = max(m[1][c], m[2][c - w[1]] + v[1]);
        }
    }
    
    //构造最优解
    public static void traceback(int[][] m, int[] w, int c, int[] x,int[]v) {
        int n = w.length - 1;
        for (int i = 1; i < n; i++) {
            if (m[i][c] == m[i + 1][c]) {
                x[i] = 0;
            } else {
                x[i] = 1;
                c -= w[i];
            }
        }
        x[n] = (m[n][c] > 0) ? 1 : 0;
        //输出
        int allWeight = 0;
        int allValue = 0;
         for (int a = 1; a < n + 1; a++) {
            System.out.print(x[a] + " ");
            if (x[a] == 1) {
                allWeight += w[a];
                allValue += v[a];
            }
        }
         System.out.println("最终装的总重量为：" + allWeight + " 总价值为：" + allValue);
         System.out.println();
    }

    public static void main(String[] args) {
        //固定样例
        int c = 15;//最多承受的容量
        int n = 5;//物品的个数
        int[] w = {0, 5, 6, 7, 8, 9};
        int[] v = {0, 10, 6, 14, 2, 3};
        int[] x = new int[n + 1];
        int[][] m = new int[n + 1][c + 1];
        
        //递归方法
        System.out.println("【递归方法】");
        System.out.println("得到的最大价值为：" + recKnapsack(n, c, w, v));
        System.out.println();
        
        //动态规划方法
        System.out.println("【动态规划方法】（1代表背包装有该物件，0代表没有装）");
        knapsack(v, w, c, m);
        traceback(m, w, c, x,v);
    }
}

最优二叉搜索树

public class BinarySearchTree {

    int flag = 0;

    void OptimalBinarySearchTree(float[] a, float[] b, float[][] m, int[][] s, float[][] w) {
        int n = a.length - 1;
        for (int i = 0; i <= n; i++) {
            w[i + 1][i] = a[i];
            m[i + 1][i] = 0;
        }
        for (int r = 0; r < n; r++) {
            for (int i = 1; i <= n - r; i++) {
                int j = i + r;
                w[i][j] = w[i][j - 1] + a[j] + b[j];
                m[i][j] = m[i + 1][j];
                s[i][j] = i;
                for (int k = i + 1; k <= j; k++) {
                    float t = m[i][k - 1] + m[k + 1][j];
                    if (t < m[i][j]) {
                        m[i][j] = t;
                        s[i][j] = k;
                    }
                }
                m[i][j] += w[i][j];
            }
        }
    }
    //构造最优解
    void backtrace(int[][] s, int i, int j) {
        if (flag == 0) {
            System.out.print("根为：" + s[i][j]);
            flag++;
        }
        if (i > j) {
            System.out.print("空");
            System.out.println("");
        }
        if (i <= j) {
            int r = s[i][j];
            if (i != 1 || j != s.length - 2) {
                System.out.print(r);
            }
            System.out.println("");
            System.out.print(r + "的左孩子是");
            backtrace(s, i, r - 1);
            System.out.print(r + "的右孩子是");
            backtrace(s, r + 1, j);
        }
    }

    public static void main(String[] args) {
        //固定样例
        float a[] = {-1f, 0.15f, 0.1f, 0.05f, 0.1f, 0.2f};
        float b[] = {0.05f, 0.1f, 0.05f, 0.05f, 0.05f, 0.1f};
        
        int n = a.length - 1;
        float[][] m = new float[n + 2][n + 2];
        int[][] s = new int[n + 2][n + 2];
        float[][] w = new float[n + 2][n + 2];
        System.out.println("最优二叉搜索树");
        //构造
        BinarySearchTree tree = new BinarySearchTree();
        tree.OptimalBinarySearchTree(a, b, m, s, w);
        //输出
        System.out.println("最小平均路长为：" + m[1][n]);
        tree.backtrace(s, 1, n);
    }
}

三、贪心算法

07. 活动安排、背包问题

活动安排

1.无结构体

#include<iostream>
using namespace std;

void greedySelect(int n, int s[], int e[], bool a[])
{
    a[1] = true;
    int j = 1;
    for(int i = 2; i <=n; i++)
    {
        if(s[i] >= e[j])
        {
            a[i] = true;
            j = i;
        }
        else
        {
            a[i] = false;
        }
    }
}

int main()
{
    //固定样例
    int s[] = {0, 1, 0, 0, 5, 3, 5, 6, 8, 8, 2, 12};
    int e[] = {0, 3, 5, 2, 7, 6, 9, 11, 15, 12, 13, 14};
    int n=sizeof(s)/sizeof(s[0])-1;
    //记录活动安排与否
    bool a[n+1];

    greedySelect(n, s, e, a);
    int num=0;
    cout << "安排结果：" << endl;
    for(int i = 1; i <= n; i++)
    {
        if(a[i])
        {
            num++;
            cout << "第"<<num<<"个："<<"是第" << i << "个活动:" << "活动时间为：" << s[i] << "--" << e[i] << endl;
        }
    }
    return 0;
}

2.有结构体

#include<stdio.h>

typedef struct
{
    int id;         // 活动编号
    int start;      // 开始时间
    int end;        // 结束时间
    int isSelected; // 是否被选择，0 否， 1 是
} activity, *Pactivity ;

void merge(activity c[], activity d[], int left, int m, int right)
{
    int i = left, j = m + 1, k = left;
    while((i <= m) && (j <= right))
    {
        if(c[i].end<=c[j].end)
            d[k++] = c[i++];
        else
            d[k++] = c[j++];
    }

    if(i > m)
        for(int q = j; q <= right; q++)
        {
            d[k++] = c[q];
        }
    else
    {
        for(int q = i; q <= m; q++)
        {
            d[k++] = c[q];
        }
    }

}
void mergePass(activity a[], activity b[], int s, int len)
{
    int i = 0;
    while(i <= len - 2 * s)
    {
        merge(a, b, i, i + s - 1, i + 2 * s - 1);
        i = i + 2 * s;
    }
    if(i + s < len)
    {
        merge(a, b, i, i + s - 1, len - 1);
    }
    else
    {
        for(int j = i; j < len; j++)
        {
            b[j] = a[j];
        }
    }
}

void mergeSort(activity act1[], int len)
{
    activity act2[len];
    int s = 1;

    while(s < len)
    {
        mergePass(act1, act2, s, len);
        s += s;
        mergePass(act2, act1, s, len);
        s += s;
    }
}

void printAll(activity act[], int n)
{
    for(int i = 1; i <= n; i++)
    {
        printf("第%d个活动为%d,时间是：%d ———— %d\n", i, act[i].id, act[i].start, act[i].end);
    }
}

void printSelected(activity act[], int n)
{
    for(int i = 1, j = 1; i <= n; i++)
    {
        if(act[i].isSelected)
            printf("第%d个被选择的活动为%d,时间是：%d ———— %d\n", j++, act[i].id, act[i].start, act[i].end);
    }
}

int greedySelector(activity activities[], int n){
    activities[1].isSelected = 1;
    int j = 1, count = 1;
    for(int i = 2; i <= n; i++){
        if(activities[i].start >= activities[j].end){
            activities[i].isSelected = 1;
            j = i;
            count++;
        }
    }
    return count;
}

int main()
{
    int n;
    printf("请输入活动个数：");
    scanf("%d", &n);

    activity activities[n+1];
    activities[0].id = activities[0].start = activities[0].end = 0;

    for(int i = 1; i <= n; i++)
    {
        printf("请输入第%d个活动的开始时间和结束时间：", i);
        scanf("%d %d", &activities[i].start, &activities[i].end);
        activities[i].id = i;
        activities[i].isSelected = 0;
    }

    // 按照结束时间非降序排列活动
    mergeSort(activities, n+1);

    printAll(activities, n);

    printf("\n总共有%d个活动被选择\n", greedySelector(activities, n));

    printSelected(activities, n);

    return 0;
}

背包问题

class Element implements Comparable {

    int id;//编号
    float v;//价值
    float w;//重量

    public Element(int i, float w, float v) {
        this.id = i;
        this.v = v;
        this.w = w;
    }

    @Override
    public int compareTo(Object o) {
        if ((this.v / this.w) < (((Element) o).v / ((Element) o).w)) {
            return -1;
        } else if ((this.v / this.w) == (((Element) o).v / ((Element) o).w)) {
            return 0;
        } else {
            return 1;
        }
    }

}

public class knapsackMaxValue {

    //利用上次实验任务的归并排序
    private static class MergeSort {
    //略
    }

    public static float knapsack(float c, float[] w, float[] v, float[] x) {
        int n = v.length;
        Element[] d = new Element[n];//d是一个接口

        for (int i = 0; i < n; i++) {
            d[i] = new Element(i, w[i], v[i]);
        }
        //归并排序
        MergeSort.mergesort(d);//按v[i]w[i]从大到小排序

        int i;
        float opt = 0;
        for (i = 0; i < n; i++) {
            x[i] = 0;
        }

        for (i = 0; i < n; i++) {
            if (d[i].w > c) {
                break;
            }
            x[d[i].id] = 1;
            opt += d[i].v;
            c -= d[i].w;
        }
        if (i < n)//部分装在
        {
            x[d[i].id] = c / d[i].w;
            opt += x[d[i].id] * d[i].v;
        }
        return opt;
    }

    public static void main(String[] args) {
        //固定样例
        float c = 50;
        int n = 3;
        float[] w = {10f, 20f, 30f};
        float[] v = {10f, 100f, 100f};
        float[] a = new float[n];
        System.out.println("最大价值为:" + knapsack(c, w, v, a));
    }
}

08. 哈夫曼编码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include<string.h>

typedef struct
{
    char CH;
    int parent, lChild, rChild;
    int weight;
} Tree; //树的结构体

typedef struct
{
    char code[30];
    int cnt;
} TreeCode;

//构建哈夫曼树
void CreateTree(Tree *hTree, int N)
{
    int m, c,i, j, min, cmin;//min-最小值，cmin-次小值
    char s;
    hTree[0].CH = ' ';
    hTree[0].parent = hTree[0].lChild = hTree[0].rChild = -1;
    printf("请输入空格和a~z字母的频度：");    //186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 80 18 1 16 1
    //输入空格的权值
    scanf("%d", &hTree[0].weight);
    //输入A~Z的权值
    for (i=1; i<N; i++)
    {
        hTree[i].CH = 'a' + i - 1;
        hTree[i].parent = hTree[i].lChild = hTree[i].rChild = -1;
        scanf("%d", &hTree[i].weight);
    }
    scanf("%c", &s);
    //最小值作为新根的左孩子，次小值作为右孩子
    for (i=N; i<2*N-1; i++)
    {
        min = 99999;
        cmin = 99999;
        m = 0;
        c = 0;//最小值和次小值的下标
        for (j = 0; j<i; j++)
        {
            if (hTree[j].parent == -1)
                if (hTree[j].weight<min)
                {
                    c = m;
                    cmin = min;
                    min = hTree[j].weight;
                    m = j;
                }
                else if (hTree[j].weight<cmin)
                {
                    cmin = hTree[j].weight;
                    c = j;
                }
        }
        hTree[i].weight = min + cmin;
        hTree[i].CH = ' ';
        hTree[i].lChild = m;
        hTree[i].rChild = c;
        hTree[m].parent = i;
        hTree[c].parent = i;
        hTree[i].parent = -1;

    }
}

//哈夫曼编码
void HfmCode(Tree *hTree, TreeCode *codeFile, int N)
{
    int i, p, c;
    TreeCode S;
    for (i = 0; i<N; i++)//对N的字符进行编码
    {
        c = i;
        p = hTree[c].parent;
        S.cnt = N;
        S.code[N] = '\0';
        while (p != -1)//要将第i个字符从它自身找到它的双亲为止
        {
            if (hTree[p].lChild == c)//第i个字符是双亲p的左孩子，S.code[]中存‘0’；
                S.code[--S.cnt] = '0';
            else//否则存‘1’
                S.code[--S.cnt] = '1';
            c = p;
            p = hTree[c].parent;
        }
        codeFile[i] = S;
    }
}

void PrintCode(TreeCode *codeFile)
{
    char str[200],s;
    int i;
    //186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 80 18 1 16 1
    printf("请输入需要编码的字符串：");
    gets(str);
    printf("该字符串编码为：");
    for (i = 0; i < strlen(str); i++)
    {
        if (str[i] == ' ')
            printf("%s", codeFile[0].code + codeFile[0].cnt);
        else
            printf("%s", codeFile[str[i] - 'a' + 1].code + codeFile[str[i] - 'a' + 1].cnt);//由于是倒着存的所以正着输出时要找到起始点
    }
    printf("\n\n");
}

int main()
{
    int N;
    char *ToBeTran,c;
    TreeCode *codeFile;//存编码信息的数组
    Tree *hTree;

    ToBeTran = (char*)malloc(sizeof(char)*40);//给ToBeTran分配空间
    codeFile = (TreeCode *)malloc(sizeof(TreeCode)*N);//给codeFile数组分配空间
    hTree = (Tree *)malloc(sizeof(Tree)*(2 * N - 1));//哈夫曼树的结点个数
    printf("请输入字符集大小:");
    scanf("%d", &N);//字符个数

    //输入频度
    CreateTree(hTree, N);//建树

    //编码
    HfmCode(hTree, codeFile, N);
    printf("\n");

    //输出编码
    PrintCode(codeFile);

    return 0;
}

09. 单源最短路径 最小生成树

单源最短路径-Dijkstra算法

public class dijkstraMinDistance {

    //单元最短路径问题的Dijkstra算法
    public static void dijkstra(int v, float[][] a, float[] dist, int[] prev) {
        int n = dist.length - 1;
        if (v < 1 || v > n) {
            return;       //v是起始顶点
        }
        boolean[] s = new boolean[n + 1];  //s存储已确定最短路径的顶点
        //初始化
        for (int i = 1; i <= n; i++) {
            dist[i] = a[v][i];         // dist[i]初始化为直接连接起始点的距离
            if (dist[i] == Float.MAX_VALUE) {
                prev[i] = 0;     //前驱节点为0的含义是无前驱
            } else {
                prev[i] = v;     //前驱节点是起始点
            }
        }
        dist[v] = 0;
        s[v] = true;                     //起始顶点放入s
        for (int i = 1; i < n; i++) {
            float temp = Float.MAX_VALUE;
            int u = v;
            for (int j = 1; j <= n; j++) {
                if ((!s[j]) && (dist[j] < temp)) {
                    u = j;
                    temp = dist[j];
                }
            }
            s[u] = true;
            for (int j = 1; j <= n; j++) {
                if ((!s[j]) && (a[u][j] < Float.MAX_VALUE)) {
                    float newdist = dist[u] + a[u][j];
                    if (newdist < dist[j]) {
                        dist[j] = newdist;
                        prev[j] = u;
                    }
                }
            }
        }
        for (int i = 2; i <= n; i++) {
            System.out.println("1-->" + i + "的最短距离是：" + dist[i] + "，且" + i + "的前驱点是：" + prev[i]);
        }
    }

    public static void main(String[] args) {
        float max = Float.MAX_VALUE;
        //ppt实例
        float[][] a = new float[][]{{0, 0, 0, 0, 0, 0},
        {0, max, 10, max, 30, 100},
        {0, max, max, 50, max, max},
        {0, max, max, max, 55, 10},
        {0, max, max, 20, max, 60},
        {0, max, max, max, max, max}};
        int v = 1;
        int n = 5;
        float[] dist = new float[n + 1];
        int[] prev = new int[n + 1];
        dijkstra(v, a, dist, prev);
    }
}

最小生成树-Prim算法

public class primTree {

    public static void prim(int n, float[][] weight) { //n为顶点数，weight为权  
        float[] lowcost = new float[n + 1]; //到新集合的最小权  
        int[] closest = new int[n + 1];  //与最小权对应的s集合的点  
        boolean[] s = new boolean[n + 1];
        //s[i] == true代表i点在s集合中  
        s[1] = true;//将第一个点放入s集合  
        for (int i = 2; i <= n; i++) {//初始化辅助数组  
            lowcost[i] = weight[1][i];
            closest[i] = 1;
            s[i] = false;
        }
        for (int i = 1; i < n; i++) {
            float min = Float.MAX_VALUE;
            int j = 1;
            for (int k = 2; k <= n; k++) {//根据最小权加入新点
                if ((lowcost[k] < min) && (!s[k])) {
                    min = lowcost[k];
                    j = k;
                }
            }
            System.out.println(closest[j] + "-->" + j + " 权值:" + min); //把部分连接树输出
            s[j] = true;//加入新点j                
            for (int k = 2; k <= n; k++) {//根据新加入的点j,求最小权
                if ((weight[j][k] < lowcost[k]) && !s[k]) {
                    lowcost[k] = weight[j][k];
                    closest[k] = j;
                }
            }
        }
    }

    public static void main(String[] args) {
        float max = Float.MAX_VALUE;
        //ppt实例
        float[][] weight = {{0, 0, 0, 0, 0, 0, 0},
        {0, max, 6, 1, 5, max, max},
        {0, 6, max, 5, max, 3, max},
        {0, 1, 5, max, 5, 6, 4},
        {0, 5, max, 5, max, max, 2},
        {0, max, 3, 6, max, max, 6},
        {0, max, max, 4, 2, 6, max}};
        int n = 6;
        prim(n, weight);
    }
}

最小生成树-Kruskal算法

public class Kruskal {
public static class EdgeNode implements Comparable {

    int weight;
    int u, v;

    public EdgeNode(int uu, int vv, int ww) {
        u = uu;
        v = vv;
        weight = ww;
    }

    public EdgeNode(int ww) {
        weight = ww;
    }

    public int compareTo(Object x) {
        int xw = ((EdgeNode) x).weight;
        if (weight < xw) {
            return -1;
        }
        if (weight == xw) {
            return 0;
        }
        return 1;
    }
}

public static class FastUnionFind {

    int u, v;
    int n;
    int[] code;

    public FastUnionFind(int nn) {
        n = nn;
        code = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            code[i] = i;
        }
    }

    public int find(int t) {
        while (t != code[t]) {
            t = code[t];
        }
        return t;
    }

    public void union(int u, int v) {
        int a = find(u);
        int b = find(v);
        if (a == b) {
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (code[i] == a) {
                code[i] = b;
            }
        }
    }
}

public static class MinHeap {

    Comparable[] E;
    int length;

    public void initialize(Comparable[] aa, int llength) {
        E = aa;
        length = llength;
        for (int i = length / 2; i > 0; i--) {
            adjustHeap(E, i, length);
        }
    }

    public void removeMin() {
        if (length > 0) {
            length = length - 1;
            swap(E, 1, length);
            adjustHeap(E, 1, length);
        }
    }

    public void returnMinHeap() {
        Comparable[] b = new Comparable[E.length];
        for (int i = 1; i <= E.length - 1; i++) {
            removeMin();
        }
    }

    public static void adjustHeap(Comparable[] E, int i, int length) {
        Comparable x = E[i];
        for (int k = 2 * i; k < length; k = 2 * k) {
            if (k + 1 < length && E[k].compareTo(E[k + 1]) > 0) {//判断是否有右孩子
                k++;
            }
            if (E[k].compareTo(x) < 0) {//判断左孩子的值是否大于节点的值
                swap(E, i, k);
                i = k;
            } else {
                break;
            }
        }
    }

    public static void swap(Comparable[] arry, int E, int b) {//交换数值
        Comparable x = arry[E];
        arry[E] = arry[b];
        arry[b] = x;
    }
}

public static boolean kruskal(EdgeNode[] E, EdgeNode[] t, int e, int n) {
    //n是顶点数；e是边数；E是图中边的集合(E的每个元素包括两个顶点及权；t是最终的生成树的边集。
    MinHeap H = new MinHeap();
    H.initialize(E, e);//按边的权重大小建最小堆

    FastUnionFind U = new FastUnionFind(n);//并查集
    int k = 0;
    while (e > 0 && k < n - 1) {
        //取出堆中最小的边
        EdgeNode x = E[1];
        H.removeMin();
        e--;
        int a = U.find(x.u);//检查所属的连通分支号
        int b = U.find(x.v);
        if (a != b) {
            t[k++] = x;//t中加入x这条边
            U.union(a, b); //将两个连通分支合并
        }
    }
    return (k == n - 1);//如果k!=n-1，说明图不连通
}

public static void display(EdgeNode[] t) {
    for (int i = 0; i < t.length; i++) {
        System.out.println(t[i].u + "--" + t[i].v + " 权值：" + t[i].weight);
    }
}

public static void main(String[] args) {
    int n = 6;
    EdgeNode[] E = new EdgeNode[2 * (n - 1) + 1];
    for (int i = 1; i <= E.length - 1; i++) {
        E[i] = new EdgeNode(i);
    }
    //ppt实例
    E[1] = new EdgeNode(1, 2, 6);
    E[2] = new EdgeNode(1, 4, 5);
    E[3] = new EdgeNode(1, 3, 1);
    E[4] = new EdgeNode(2, 3, 5);
    E[5] = new EdgeNode(2, 5, 3);
    E[6] = new EdgeNode(3, 4, 5);
    E[7] = new EdgeNode(3, 5, 6);
    E[8] = new EdgeNode(3, 6, 4);
    E[9] = new EdgeNode(4, 6, 2);
    E[10] = new EdgeNode(5, 6, 6);

    EdgeNode[] t = new EdgeNode[n - 1];

    int e = E.length - 1;
    boolean flag = kruskal(E, t, e, n);
    if (flag == true) {
        System.out.println("图连通");
    } else {
        System.out.println("图不连通");
    }
    display(t);
}

}

四、回溯法

10. 子集树、装载问题

子集树

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

void printVector(vector<int> array )
{
    for(int i = 0; i <array.size(); i++)
        cout << array[i]<< " " ;
    cout << endl;
}

void dfs(vector<int>& array, int dep)
{
    int size = array.size();

    if(dep == size)
    {
        printVector(array);
        return;
    }
    //i的取值为0,1
    for(int i = 0; i < 2; i++)
    {
        array[dep] = i;
        dfs(array, dep+1);
    }
}

int main()
{
    vector<int> b;
    int n;
    cout<<"请输入个数：";
    cin>>n;
    b.resize(n, 0);
    dfs(b, 0);
    return 0;
}

装载问题

public class SubsetTree {
    //类数据成员
    static int n;//集装箱数目 
    static int[] w;//集装箱重量数组
    static int c;//第一艘船的重量
    static int cw;//当前装载的重量
    static int bestw;//目前最优装载的重量
    
    static int r;//剩余货箱的重量
    static int[] x;//当前解，记录从根至当前结点的路径
    static int[] bestx;//记录当前最优解

    public static int MaxLoading(int[] ww, int cc) {
        //初始化类成员
        n = ww.length - 1;
        w = ww;
        c = cc;
        cw = 0;
        bestw = 0;
        x = new int[n + 1];
        bestx = new int[n + 1];
        //初始化r
        for (int i = 1; i <= n; i++) {
            r += w[i];
        }
        //计算最优载重量
        backtrack(1);
        return bestw; 
    }

    //回溯算法
    public static void backtrack(int i) {
        //搜索第i层结点
        if (i > n) {//到达叶节点
            if (cw > bestw) {
                for (int j = 1; j <= n; j++) {
                    bestx[j] = x[j];
                }
                bestw = cw;
            }
            return;
        }
        //搜索子树
        r -= w[i];
        if (cw + w[i] <= c) {//搜索左子树
            x[i] = 1;
            cw += w[i];
            backtrack(i + 1);
            cw -= w[i];//回溯
        }

        if (cw + r > bestw) {
            x[i] = 0;//搜索右子树
            backtrack(i + 1);
        }
        r += w[i];
    }

    public static void main(String[] args) {

        int[] ww = {0, 20, 30, 60, 40, 40};
        int c1 = 100;
        int c2 = 100; 
        int n = ww.length - 1;
        MaxLoading(ww, c1);
        int weight2 = 0;//第二集装箱可能要装的重量
        for (int i = 1; i <= n; i++) {
            weight2 += ww[i] * (1 - bestx[i]);
        }
        if (weight2 > c2) {
            System.out.println("无法载满货物");
        } else {            
            //第一个集装箱的装载情况
            for (int i = 1; i <= n; i++) {
                if (bestx[i] == 1) {
                    System.out.println("第" + i + "件货物装入第一个集装箱");
                }
            }
            //第二个集装箱的装载情况
            for (int i = 1; i <= n; i++) {
                if (bestx[i] == 0) {
                    System.out.println("第" + i + "件货物装入第二个集装箱");
                }
            }
            System.out.println("第一个集装箱装载货物的重量： " + bestw);
            System.out.println("第二个集装箱装载货物的重量： " + weight2);
        }
    }
}

11. 子集和问题、n后问题

子集和问题

给定n个正整数W=(w1, w2, …, wn)和正整数M，是否存在W的一个子集，该子集的和等于M。输出该子集。

#include<stdio.h>
#define MAXN 20

int n=4,W=31;
int w[]= {0,10,13,23,8};
int count=0;

void display(int x[])
{
    int i;
    printf("第%d个解：",++count);
    for(int i=1; i<=n; i++)
        if(x[i]==1)
            printf("%d ",w[i]);
    printf("\n\n");
}

void dfs(int tw,int rw,int x[],int i) //求解子集和
{
    if(i>n)
    {
        if(tw==W)
            display(x);
    }
    else
    {
        if(tw+w[i]<=W)
        {
            x[i]=1;
            dfs(tw+w[i],rw-w[i],x,i+1);
        }
        if(tw+rw>W)
        {
            x[i]=0;
            dfs(tw,rw-w[i],x,i+1);
        }
    }
}
int main()
{
    int x[MAXN];
    int rw=0;
    for(int j=1; j<=n; j++)
        rw+=w[j];
    dfs(0,rw,x,1);
	return 0;
}

n后问题

public class NQueen {

    static int n;      //皇后个数
    static int[] x;    //当前解
    static long sum;   //当前已找到的可行方案

    public static long nQueen(int nn) {
        n = nn;
        sum = 0;
        x = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            x[i] = 0;
        }
        backtrack(1);
        return sum;
    }

    private static void backtrack(int t) {
        if (t > n) {
            sum++;
        } else {
            for (int i = 1; i <= n; i++) {
                x[t] = i;
                if (place(t)) {
                    backtrack(t + 1);
                }
            }
        }
    }

    private static boolean place(int k) {
        for (int j = 1; j < k; j++) {
            if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || (x[j] == x[k])) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("请输入皇后的个数：");
        int nn = input.nextInt();
        System.out.println("当皇后个数为"+nn+"时，可行方案为："+nQueen(nn)+"个");
    }
}

12. 单源最短路径、着色问题、旅行售货员

单源最短路径

public class BBShortest {
    static float[][] a;     //  图G的邻接矩阵
    static int v;           //  起点编号
    static float[] dist;    //  dist[i]是节点i与起点的当前算得的最短距离
    static int[] p;         //  前驱数组

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.println("请输入结点个数");
        int n = s.nextInt();

        a = new float[n+1][n+1];
        for(int i = 0; i < a.length; i++){
            Arrays.fill(a[i], Float.MAX_VALUE);
        }
        p = new int[n+1];
        dist = new float[n+1];

        System.out.println("请输入边数");
        int e = s.nextInt();
        for (int i = 0; i < e; i++) {
            System.out.println("请输入两点及其距离");
            int previous = s.nextInt();
            int next = s.nextInt();
            a[previous][next] = s.nextFloat();
        }

        shortest(1, dist, p);

        // 从左到右，按列优先依次为1，2，3,,,
        System.out.println("最短距离为：" + dist[n] + "\n最短路径为：");
        back(p[n]);
        System.out.println(n);
    }

    static class HeapNode implements Comparable {
        int i;              // 顶点编号
        float length;       // 当前路长

        public HeapNode(int i, float length) {
            this.i = i;
            this.length = length;
        }

        @Override
        public int compareTo(Object o) {
            float xl = ((HeapNode) o).length;
            if (length < xl) {
                return -1;
            }
            if (length == xl) {
                return 0;
            }
            return 1;
        }
    }

    public static void shortest(int v, float[] dist, int[] p) {
        int n = p.length - 1;
        MinHeap heap = new MinHeap(n);
        //定义源为初始扩展结点
        HeapNode enode = new HeapNode(v, 0);

        //dist[j]表示当前结点j到起点的最短距离，初始化为最大值
        for (int j = 1; j <= n; j++)
            dist[j] = Float.MAX_VALUE;
        dist[v] = 0;

        while (true) {      // 搜索问题的解空间
            for (int j = 1; j <= n; j++)
                // enode.i是当前的扩展节点， enode.length是该节点到起始点的最短距离
                if (a[enode.i][j] < Float.MAX_VALUE && enode.length + a[enode.i][j] < dist[j]) {
                    // enode.i 到顶点j可达，且满足控制约束
                    dist[j] = enode.length + a[enode.i][j];
                    //dist[j]是节点J与起点的当前算得的最短距离
                    p[j] = enode.i;    // p[j]表示p的前驱节点
                    HeapNode node = new HeapNode(j, dist[j]);
                    heap.insert(node);      // 加入活结点优先队列
                }
            if (heap.isEmpty()) break;
            else enode = heap.removeMin();
        }
    }

    static void back(int i){
        if(p[i] == 0){
            System.out.print(i + " -> ");
        }else{
            back(p[i]);
            System.out.print(i + " -> ");
        }
    }
}

// 下标从0开始的最小堆， 子节点 2n+1, 2(n+1)
class MinHeap {
    //存储堆中元素
    private BBShortest.HeapNode[] items ;
    //记录堆中元素个数
    private int total;

    public MinHeap() {

    }

    public MinHeap(int capacity) {
        this.items = new BBShortest.HeapNode[capacity];
        for (int i = 0; i < capacity; i++) {
            this.items[i] = new BBShortest.HeapNode(i, 0);
        }
    }

    //获取队列中元素个数
    public int size() {
        return total;
    }

    //判断队列是否为空
    public boolean isEmpty() {
        return total == 0;
    }

    //判断堆中索引i处的元素是否小于索引j处的元素
    private boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }

    //交换堆中i索引和j索引处的值
    private void swap(int i, int j) {
        BBShortest.HeapNode tmp = items[i];
        items[i] = items[j];
        items[j] = tmp;
    }

    //往堆中插入一个元素
    public void insert(BBShortest.HeapNode t) {
        items[++total] = t;
        swim(total);
    }

    //删除堆中最小元素，并返回这个最小元素
    public BBShortest.HeapNode removeMin() {
        BBShortest.HeapNode min = items[0];
        swap(0, total);
        total--;
        sink(0);
        return min;
    }

    //使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
    private void swim(int k) {
        //通过循环比较当前节点和其父节点的大小
        while (k > 0) {
            if (less(k, (k - 1) / 2)) { // 若果该节点比父节点
                swap(k, (k - 1) / 2);
            }
            k = (k - 1) / 2;
        }
    }

    //使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
    private void sink(int k) {
        //通过循环比较当前节点和其子节点中较小值
        while (2 * k + 1 <= total) { // 说明该节点有子节点
            //找到子节点中的较小值
            int min;
            if (2 * k + 2 <= total) { // 有右子节点，选左右子结点中值小的赋值给min
                if (less(2 * k + 1, 2 * k + 2)) {
                    min = 2 * k + 1;
                } else {
                    min = 2 * k + 2;
                }
            } else {
                min = 2 * k + 1;
            }
            //判断当前节点和较小值的大小
            if (less(k, min)) {     //该节点小于两个子节点
                break;
            }
            swap(k, min); //交换该节点和较小子节点
            k = min;
        }
    }
}

着色问题

public class Coloring {
    static int n, m;            // 图的顶点数，可用颜色数
    static boolean[][] a;       // 图的邻接矩阵
    static int[] x;             // 当前解
    static long sum;            // 当前已找到的可m着色方案数

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.println("输入图的顶点数，可用颜色数");
        n = s.nextInt();
        m = s.nextInt();
        x = new int[n + 1];
        a = new boolean[n + 1][n + 1];

        int xx, yy;

        while (true) {
            System.out.println("请输入相邻点对 x y");
            xx = s.nextInt();
            if (xx == -1)
                break;
            yy = s.nextInt();
            a[xx][yy] = true;
            a[yy][xx] = true;
        }

        System.out.println("可用方案数为：" + mColoring(m));

        s.close();
    }

    static long mColoring(int mm) {
        m = mm;
        sum = 0;
        backtrack(1);
        return sum;
    }

    private static void backtrack(int t) {
        if (t > n) { // 到达叶节点，表示该方案可行
            sum++;  // 可行解数量加1，并输出可行解
            System.out.print("方案" + sum + ":  ");
            for (int i = 1; i <= n; i++) {
                System.out.print(x[i] + "\t");
            }
            System.out.println();
        } else {
            for (int i = 1; i <= m; i++) {  //m叉树
                x[t] = i;
                if (ok(t))              // 继续遍历叶结点
                    backtrack(t + 1);
                x[t] = 0;
            }
        }
    }

    private static boolean ok(int k) {
        for (int j = 1; j <= n; j++) {
            if (a[k][j] && (x[j] == x[k])) //  a[k][j]：相邻接， x[j] == x[k] 同色
                return false;
        }
        return true;
    }
}

旅行售货员

public class TSP {
    static int n;       // 图G顶点数
    static int[] x;     // 当前解
    static int[] bestx; // 当前最优解
    static float bestc = Float.MAX_VALUE; // 当前最优值
    static float cc;    // 当前费用
    static float[][] a; // 图G的邻接矩阵

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.println("请输入顶点数");
        n = s.nextInt();

        init(n);
        input(s);
        print();
        s.close();
    }

    private static void input(Scanner s) {
        System.out.println("请输入相邻的两个点的编号和距离（输入-1结束）：");
        int xx, yy;
        while (true) {
            xx = s.nextInt();
            if (xx == -1)
                break;
            yy = s.nextInt();
            a[yy][xx] = a[xx][yy] = s.nextFloat();
        }
    }

    private static void print() {
        System.out.println("最短距离为：" + tsp(bestx));
        System.out.print("路径为：");
        for (int i = 1; i < x.length; i++) {
            System.out.print(bestx[i] + "\t");
        }

        System.out.println(1);
    }

    private static void init(int n) {
        x = new int[n + 1];
        bestx = new int[n + 1];
        a = new float[n + 1][n + 1];

        for (int i = 0; i < a.length; i++) {
            Arrays.fill(a[i], Float.MAX_VALUE);
        }
    }

    public static float tsp(int[] v) {
        // 置x为单位排列
        x = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            x[i] = i;
        }
        bestx = v;
        cc = 0;
        // 搜索x[2:n]的全排列
        backtrack(2); // 直接从第二个城市开始
        return bestc;
    }

    private static void backtrack(int i) { //这里的i代表第i步去的城市而不是代号为i的城市
        if (i == n) {
            // a[x[n - 1]][x[n]] < Float.MAX_VALUE 最后一个点和倒数第二个点是否有连通
            if (a[x[n - 1]][x[n]] < Float.MAX_VALUE && a[x[n]][1] < Float.MAX_VALUE &&
                    (bestc == Float.MAX_VALUE || cc + a[x[n - 1]][x[n]] + a[x[n]][1] < bestc)) {
                for (int j = 1; j <= n; j++) {
                    bestx[j] = x[j];
                }
                bestc = cc + a[x[n - 1]][x[n]] + a[x[n]][1];
            }
        } else {
            for (int j = i; j <= n; j++) {
                // 是否可进入x[i]子树
                if (a[x[i - 1]][x[j]] < Float.MAX_VALUE &&
                        (bestc == Float.MAX_VALUE || cc + a[x[i - 1]][x[j]] < bestc)) {// 搜索子树
                    swap(x, i, j);
                    cc += a[x[i - 1]][x[i]];
                    backtrack(i + 1);
                    cc -= a[x[i - 1]][x[i]];
                    swap(x, i, j);
                }
            }
        }
    }

    private static void swap(int[] x, int i, int j) {
        int temp = x[i];
        x[i] = x[j];
        x[j] = temp;
    }
}