贪心算法

贪心策略一旦经过证明成立后，它就是一种高效的算法。 可惜的是，它需要证明后才能真正运用到题目的算法中。 一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。 贪心法的应用算法有Dijkstra的单源最短路径和Chvatal的贪心集合覆盖启发式

找零钱(有可能不是最优)

用的零钱尽可能少 target = 666 3张100的，10张50的，7张5元的，44张2元，99张1元

解法

先用最大面额的

活动选择

某天要安排n个活动，要求安排的活动尽可能多 第k个活动的开始时间和结束时间分别是s[k],f[k]

解法

按照结束时间排序 每次安排最先结束的活动

最小生成树 prim

int minimum(CloseDge &c,int num)
{
    int k=num,i;
    VRType min;
    for(i=0;i<num;i++)
    {
        if(c[i].lowcost!=0)
        {
            k=i;
            min=c[i].lowcost;
            break;
        }
    }
    for(i=k+1;i<num;i++)
    {
        if(c[i].lowcost!=0&&c[i].lowcost<min)
        {
            min = c[i].lowcost;
            k = i;
        }
    }
    money+=min;
    return k;

}

void MiniSpanTree_PRIM(MGraph G, VertexType u)
{
    int k = LocateVex(G,u);
    int num = G.vexnum;

    int j,i;
    for(j=0;j<G.vexnum;++j)
        if(j!=k)
        {
            closedge[j].adjvex = u;
            closedge[j].lowcost = G.arcs[k][j].adj;
        }
    closedge[k].lowcost = 0;
    for(i=1;i<G.vexnum;i++)
    {
        k = minimum(closedge,num);

        canal[i-1][0] = closedge[k].adjvex;
        canal[i-1][1] = G.vexs[k];
        closedge[k].lowcost = 0;

        for(j=0;j<G.vexnum;j++)//更新距离 
            if(G.arcs[k][j].adj<closedge[j].lowcost)
            {
                closedge[j].adjvex = G.vexs[k];
                closedge[j].lowcost = G.arcs[k][j].adj;
            }
    }
 }

拓扑排序

void FindInDegree(ALGraph G)
{
    for(int i=0;i<G.vexnum;i++)
        indegree[i] = 0; 
    for(int i=0;i<G.vexnum;i++)
    {
        for(ArcNode* p = G.vertices[i].first_in_arc;p;p=p->nextarc)
    {
        indegree[i]++;
    }
}
}
stack<int>S;
Status TopologicalSort(ALGraph G)
{
    FindInDegree(G);

    int i,k,count;
    ArcNode* p;
    for(i=0;i<G.vexnum;++i)
        if(!indegree[i]) S.push(i);
    count = 0;
    while(!S.empty())
    {
        i=S.top();
        S.pop();
        cout<<i<<"    "<<G.vertices[i].data<<endl;
        ++count;
        for(p = G.vertices[i].firstarc;p;p=p->nextarc)
        {
            k = p->adjvex;
            if(!(--indegree[k])) S.push(k);
        } 
    }
    if(count<G.vexnum) return -1;
    else return 1;
}

关键路径

Status CriticalPath(ALGraph G)
{
    if(!TopologicalOrder(G)) return -1;

    for(int i=0;i<G.vexnum;i++)
        vl[i] = ve[G.vexnum-1];

    int j,k,dut;
    ArcNode *p;
    while(!T.empty())
    {
        j = T.top();
        T.pop();
        for(p=G.vertices[j].firstarc;p;p=p->nextarc)
        {
            k=p->adjvex;
            dut = *(p->inof);
            if(vl[k]-dut<vl[j]) vl[j] = vl[k]-dut;
        }
    }

    cout<<"关键路径为：    "; 
    for(j=0;j<G.vexnum;j++)
    {
        if(ve[j]==vl[j])
        {
            cout<<G.vertices[j].data;
            if(j!=G.vexnum-1) cout<<" -> "; 
        }
    }
    cout<<endl;
 }

最短路径Dijkstra

'''计算最短路径，采用邻接矩阵存储
若使用邻接表存储，然后使用最小堆存储未结束的点，会使find min distance更快，复杂度降为mlog(n)
'''

DIS = [    [0, 3, 10, 2], 
        [3, 0, 6, 1], 
        [10, 6, 0, 9], 
        [2, 1, 9, 0]]
print(DIS)

MIN_DIS = {}
for i in range(4):
    MIN_DIS[i] = DIS[i][0]
MIN_DIS.pop(0)

for i in range(len(DIS) - 1):
    cur_min = min(MIN_DIS.values())  # 找到当前剩下的最近的距离
    for key in MIN_DIS:
        if MIN_DIS[key] == cur_min:  # 找到对应的下标
            MIN_DIS.pop(key)  # 删除这个最小边的点
            print(key, cur_min)
            for least_dot in MIN_DIS:  # 更新距离
                if MIN_DIS[least_dot] > (DIS[key][least_dot] + cur_min):
                    MIN_DIS[least_dot] = (DIS[key][least_dot] + cur_min)
            break

Huffman编码

字符编码部分 ```cpp //从叶子结点开始逆向求每个字符的Huffman编码 HC = (HuffmanCode)malloc((n+1)sizeof(char));//分配n个字符编码的头指针向量 char cd = (char )malloc(n*sizeof(char)); //存储01编码 cd[n-1] = '\0';

int start; for(i=1;i<=n;i++) { start = n-1; int c,f; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild == c) cd[--start] = '0';//if "0" else cd[--start] = '1'; HC[i] = (char)malloc((n-start)sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd); ```