算法分析与设计——实验3：贪心算法_算法设计与分析实验三贪心法

//prim和kruskal贪心算法解决最小生成树
#include<iostream>
#include<cstring>
using namespace std;
 
int n;       //结点个数
int m;       //边条数
int map[101][101]; //无向图
int pre[101];
int u[101], v[101], edge[101];  //u,v分别为两个点，edge为两个点之间的边
 
int find(int x) {
    int root = x;
    while (pre[root] != root)  root = pre[root];
    return root;
}
 
//最小生成树prim算法
void prim() {
    int count = 0;
    cout << "prim算法求解：" << endl;
    int dist[101];          //dist[i]存放树中各点到i点的最短边权值
    int closest[101];       //closest[i]存放树中哪个点到i点的边为最短边
    bool s[101];            //记录i点是否已连入
 
    //初始化
    for (int i = 1; i <= n; i++) {
        dist[i] = map[1][i];
        s[i] = false;
        closest[i] = 1;
    }
 
    s[1] = true;
    for (int i = 1; i < n; i++) {
        //最小生成树只有n-1条边
        int min = 100000;
        int k = 1;
        for (int j = 2; j <= n; j++) {
            //找最小边
            if ((dist[j] < min) && (!s[j])) {
                min = dist[j];
                k = j;
            }
        }
        cout << k << "-->" << closest[k] << ": " << min << endl;
        count += min;
        s[k] = true;
        for (int j = 1; j <= n; j++)
        {
            if ((map[k][j] < dist[j]) && (!s[j])){
      //如果新的结点到j的边比原来的结点到j的边小，就用新结点替换掉原结点
                dist[j] = map[k][j];
                closest[j] = k;
            }
        }
    }
    cout << "最小权重和为：" << count << endl;
}
 
//最小生成树kruskal算法
void kruskal() {
    cout << "kruskal下解为:" << endl;
    int minNum, fu, fv;
    int count = 0;
    int total = n - 1;
    while (total > 0){
        int min = 10000000;
        for (int i = 1; i <= m; i++){
            //找最小值
            if (u[i] == -1 || v[i] == -1)  continue;
            if (edge[i] < min) {
                min = edge[i];
                minNum = i;
            }
        }
        fu = find(u[minNum]);
        fv = find(v[minNum]);
        if (fu != fv){
            //不连通,就连接两个点
      cout << v[minNum] << "-->" << u[minNum] << ": " << edge[minNum] << endl;
            count += edge[minNum];
            pre[fu] = fv;
            total--;
        }
        edge[minNum] = 100000000;  //改变已经找到的最小值
        u[minNum] = -1;
        v[minNum] = -1;
    }
    cout << "最小权重和为：" << count << endl;
}
 
int main()
{
    cout << "输入结点个数以及边条数：" << endl;
    cin >> n >> m;
    int i, a, b, tem;
    memset(map, 0x3f, sizeof(map));
    cout << "输入对应两结点序号以及两点间边的权重：" << endl;
    for (i = 1; i <= n; i++) pre[i] = i;
    for (i = 1; i <= m; i++) {
        cin >> a >> b;
        cin >> tem;
        map[a][b] = map[b][a] = tem;
        u[i] = a;
        v[i] = b;
        edge[i] = tem;
    }
    prim();
    kruskal();
    return 0;
}

//利用贪心算法找零
#include <iostream>
using namespace std;
 
int main() {
    int number;
    cout << "请输入你的找零值(单位：分)：";
    cin >> number;
    double a[4]={25,10,5,1};        //保存已有面值硬币(单位：分)
    double b[4]={0,0,0,0};          //保存找出的每种硬币的数量
 
    for(int i = 0; i < 4; i++) {
        int x = 0;   //记录硬币数量
        while(number >= a[i]) {
            x++;
            number -= a[i];
        }
        b[i] = x;
    }
    cout<<"25 分: "<<b[0]<<endl;
    cout<<"10 分: "<<b[1]<<endl;
    cout<<"5  分: "<<b[2]<<endl;
    cout<<"1  分: "<<b[3]<<endl;
 
    return 0;
}

#include <iostream>
using namespace std;
 
int n;   //顶点个数
int m;   //边数
int a [10000][10000];   //邻接矩阵
int dist [10000];       //dist[i]记录顶点v到i点的距离
int pre [10000];       //pre[i]记录i点前驱节点
int v = 1 ;        //顶点
void dijkstra();
 
int main() {
    cout << "请输入图的顶点个数和边的条数：" << endl;
    cin >> n >> m ;
 
    //初始化邻接矩阵
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            a[i][j] = -1;
        }
    }
 
    cout << "请输入图的路径长度(格式：起点 终点 长度)：" << endl;
    for(int i = 1; i <= m; i++) {
        int start, end, length ;
        cin >> start >> end >> length;
        if(start >= 1 && start <= n && start >= 1 && end <= n) {
            //无向有权图
            a[start][end] = length;
            a[end][start] = length;
        }
    }
    dijkstra();
}
 
void dijkstra() {
    if(v > 0 && v <= n) {
        bool s[n];      //顶点是否放入的标志
 
        //初始化
        for(int i = 1; i <= n; i++) {
            dist[i] = a[v][i];  //初始化为 v 到 i 的距离
            s[i] = false;       //初始化顶点未放
            if(dist[i] == -1) {
                pre[i] = 0;    //v到i无路,i的前驱节点置空
            }else {
                pre[i] = v;
            }
        }
 
        dist[v] = 0;    //v到v的距离是0
        s[v] = true;    //顶点放入
 
        for(int i = 1; i <= n - 1; i++) {
            int temp = 1000000;
            int u = v;      //u为下一个被放入的节点
 
            //这个for循环为第二步，观测域为v的观测域
            //遍历所有顶点找到下一个距离最短的点
            for(int j = 1; j < n; j++) {
                //j未放入，且v到j有路，且v到当前节点路径更小
                if(!s[j] && dist[j] != -1 && dist[j] < temp) {
                    u = j;
                    temp = dist[j];     //temp始终为最小的路径长度
                }
            }
            s[u] = true;    //将得到的下一节点放入
 
            //这个for循环为第三步，用u更新观测域
            for(int k = 1; k <= n; k++) {
                if(!s[k] && a[u][k] != -1) {
                    int newDist = dist[u] + a[u][k];
                    if(newDist < dist[k] || dist[k] == -1) {
                        dist[k] = newDist;
                        pre[k] = u;
                    }
                }
            }
        }
    }
 
    cout << v << "节点是源节点！" << endl;
    for(int i = 2; i <= n; i++) {
        cout <<"节点" << v << "到节点" << i << "最短距离是：" << dist[i] << " ；前驱点是：" << pre[i] << endl;
    }
}