8.12 PayMoney

#include<bits/stdc++.h>
//8.12  付款问题  找零钱 比如找4块六毛
//设 数组 monet【6】存储纸币面值，为避免进行实数运算，将纸币的面额扩大十倍

int PayMoney(double sum)
{
    int money[6] = {50,20,10,5,2,1};
    int i , count = 0, n = sum * 10;
    while (n > 0)
    {
        for (int i = 0; i < 6; i ++)
        {
            if (n >= money[i])
            {
                count ++;
                std::cout << "pay: " << (double)money[i]/10 << " $" << std:: endl;
                n = n - money[i];
                break;
            }

        }
    }
    return count;
}

int main() {


    PayMoney(4.6);
    return 0;
}

8.21 TSP问题

#include <iostream>
// TSP问题 是指旅行家要旅行n个城市， 要求经历各个城市且仅 经历一次 然后返回到出发的城市，并要求所走的路线最短。


// g【i】【j】 存储节点之间的代价；
// input :   无向带权图 G =（V，E）， 出发节点 w；
// output :  TSPlength；
const int N  = 10010;
int n;
int g[5][5];

int TSP(int g[5][5], int n, int w) //n个顶点 w是出发点
{
    int edgeCount = 0, TSPlength = 0;  // edgeCount 代表 连接到的边数
    int min, u, v, j;
    int flag[n] = {0};   //初始顶点均尚未加入哈密顿回路
    u = w; flag[w] = 1;  //从初始结点开始 将其加入回路
    while (edgeCount < n - 1)     // 循环直到边数等于 n - 1 代表连通了所有的顶点
    {
        min = 100;//假设100是最远的距离 代表不可达
        for (j = 0; j < n; j ++)    //求临边距离的最小值
        {
            if ((flag[j] == 0) && (g[u][j] != 0) && (g[u][j]) < min) // 如果j顶点 还没加入 并且可达 并且是距离当前顶点最近的
            {
                v = j; min = g[u][j];   // v为待加入的顶点   距离最小值不断更新
            }
        }
        TSPlength += min;
        flag[v] = 1; edgeCount ++; //将V并入
        std::cout << u << "-->" << v << std::endl; // u --> v
        u = v;  // 更新当前顶点为 v;
    }
    std::cout << u << "-->" << w << std::endl;  //输出最后的回边
    return TSPlength + g[u][w];  //加上回去的路径长度并返回

}



int main() {
    n = 5;
    for (int i = 0; i < 5; i ++)
        for (int j = 0; j < 5; j ++)
            std::cin >> g[i][j];

    int ans;
    ans = TSP(g, n, 0);
    std:: cout << ans << std::endl;
    return 0;
}

8.31 背包问题

#include <bits/stdc++.h>

void Sort(int n,int w[],int v[])
{
    int i,j;
    double temp1,temp2;
    for(i=0;i<n;i++)
        for(j=0;j<n-i;j++)//冒泡排序
        {
            temp1=(double)v[j]/w[j];
            temp2=(double)v[j+1]/w[j+1];
            if(temp1<temp2)
            {

                std::swap(w[j],w[j+1]);
                std::swap(v[j],v[j+1]);
            }
        }

}

//背包问题 可以选一部分加入 类似于装饮料
double knap(int w[], int v[], int n, int c) // v:体积 w: wealth c capecity
{
    double x[n] = {0}, maxValue = 0;
    int i;
    for (int i = 0; w[i] < c; i ++)
    {
        x[i] = i;
        maxValue += v[i];
        c = c - w[i];
    }
    x[i] = (double)c/w[i];
    maxValue += x[i] * w[i];
    return maxValue;
}

int main() {
    int n  = 3, w[n] ={60, 20, 20}, v[n] = {10, 200, 60}, c =50;
    Sort(n,w,v);

        int ans = knap(w , v, n, c);
    std::cout << "maxValue is  " <<  ans << std::endl;
    for(int i = 0; i < n; i ++)
        std::cout  << v[i] << std::endl;

    return 0;
}

8.23最小生成树prim

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N =510,INF=0x3f3f3f3f;
int g[N][N], dist[N];
int n,m;
bool st[N];
int res=0;//res存的是最小生成树里面所有边的长度之和

int prim()
{
    memset(dist, INF, sizeof dist);

    for(int i = 0; i < n; i ++) //一共 n次 没有定初始的节点
    {
       int t = -1;
       for (int j = 1; j <= n; j++) //找距离集合最短的点
       {
            if (!st[j] && (t == -1 || dist[j] < dist[t])) {//没有加入集合中的 距离最短的
                t = j;
            }
        }
        if(i && dist[t]==INF) return INF;//如果不是第一个点而且能找到的距离还等于无穷 说明图不连通 直接返回impossible;
         st[t]=true;

        if (i) res += dist[t];//不是第一个点的话就 就把边长加进去
        for(int i=1;i<=n;i++)
        {
            dist[i]=min(dist[i],g[t][i]);//一样的 用 T来更新周围的点
        }

    }

    return res;  
}

int main()
{
    memset(g,0x3f,sizeof g);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    int t = prim();
    if (t == INF) puts("impossible");
    else cout << t << endl;
}

8.23最小生成树Kruskal

#include<bits/stdc++.h>

using namespace std;

const int N = 1000010, INF = 0x3f3f3f3f;

int n, m;

int p[N];

int find(int x)  // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

struct edges
{
    int a, b, w;
   bool operator<(const edges& W) const
    {
        return w < W.w;
    }
}edges[N];

int kruskal()
{
    sort(edges, edges + m);
    for (int i = 1; i <= n; i ++ )
    {
         p[i] = i;  //初始化并查集
    }

    int res = 0, cnt = 0;


    for (int i = 0; i < m; i++) {  //克鲁斯卡尔 只遍历 边就可以了
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a), b = find(b);   // a b 的根
        if (a != b) { //判断是否连同 通过并查集的方法
            p[a] = b;
            res += w;   //最小生成树的边长度
            cnt ++;     //cnt存当前加入了多少条边
        }
    }
    if (cnt < n - 1) { //说明不连通 经典的办法
        return INF;
    }
    return res;
}


int main()
{   
    cin >> n >> m;  // n 个顶点 m 条边
    for (int i = 0; i < m; i ++)
    {
        int a, b, w; // a b 是顶点号 从 a 到 b 边的权重 为 w
        cin >> a >> b >>w;
        edges[i] = {a, b, w};  //edges 只存边
    }

    int t = kruskal();
    if (t == INF) cout << "impossible" << endl;
    else  cout << t << endl;

    return 0;

}