Try to be a good coder and emmm… review !

优化问题

优化问题的概念

即通过一定条件约束，对一组变量进行操作，使目标到达最优值。

优化问题的一般描述

优化问题的描述：

1.问题的解为一复杂结构 (x1,x2,…,xn) xi∈Si（可选的方式）

2.约束条件：B(x1,x2…,xn)，使B为true的元组称为可行解

3.目标函数f(x1,…,xn)

优化解即指使目标函数取得最值的可行解，对应的目标函数值称为优化值

贪心算法是求近似解的一种主要途径。

---

贪心算法的思想及要点

思想

  贪心算法是一种多步求解优化问题的方法，每步按一种局部最优的策略选择解的一个分量，算法以第n步结束时构造出问题的解。

  该算法问题在于：其贪婪的短视导致在很多情况下都会错过最优解，因为贪心算法不会从整体上对问题进行思考，只会埋头于当前情况。所以贪心算法不能用来求最大最小值、无法保证最后的解是最优的、只能求某些特定的解。

  所以实际上可以用贪心算法求得最优解的情况很少，所以我们要证明每一步所作的贪心选择最终能导出问题最优解。

Don’t worry. The codes here are simple and easy.

特点

1. 不回溯
2. 局部优化策略可以减小开销，但不保证得到精确优化解
3. 不同贪心策略得到不同算法
4. 常使用使目标函数有最大增量的策略为贪心策略

---

货箱装船问题

下面我们来看一个很简单的例题

例 Loading Problem

设有n个集装箱,集装箱大小一样，第i个设有n个集装箱,集装箱大小一样，第i个集装箱的重量为wi(1≤i≤n),设船的载重量为c.试设计一装船的方法使得装入的集装箱数目最多

 

这是一道很基础的贪心算法题目，我们先按照优化问题的格式来描述一下他：

令问题的解为(x1,x2,…,xn)  xi={0,1}//代表第i个箱子是否装载。

问题的约束条件是Σi=1,n wixi<=c; //装载箱子的总重量小于等于C

目标函数为 Σi=1,n xi； //装载的集装箱个数

我们的目标是极大化目标函数。

因为目标函数是所装的集装箱数目，所以按照我们的常规思想，那么一定先装重量轻的集装箱。

所以可以写出代码如下

#include <iostream>
#include <algorithm>

using namespace std;

int n,c;
int weight[100]={0};
int countt=0;
int tem_weight=0;
int main()
{
    cin>>n;
    cin>>c;
    for(int i=0;i<n;i++)
    cin>>weight[i];
    sort(weight,weight+n);
    for(int i=0;i<n;i++)
    {
        if(tem_weight+weight[i]<=c)
        {
            tem_weight+=weight[i];
            countt++;
        }
        else {break;}
    }
    cout<<countt<<endl;
    return 0;
}

这时你可能对这种贪心策略存疑，先装载重量低的箱子一定能得到最优解吗？

下面给出证明

证明:

设问题最优解为(y1,y2,…,yn)

如最优解不含箱子1，将箱子1替换优化解中某一个箱子得到一个新的解

1.替换是必须的：若1还能装入船中，则(y1,y2,…,yn)不是优化的

2.因为1是最轻的，所以替换后的解仍是可行的

3.替换后的解装入的箱子数==优化的箱子数，它仍是优化解

4.替换后新的优化解和贪心解都有箱子1

反复替换得到一个优化解，优化解==贪心解

替换次数是有穷的。

这就确定了在这道题目里，我们的贪心解一定是优化解。

针对这个问题也引出一点：贪心解虽然在一种策略下只有一个，但问题的真正最优解可能有多个。

---

0/1背包问题

01背包问题

设有容量c的背包和n件物品，物品i的重量为wi ;假定装入物品i获得的效益值为pi,试给出一装入物品的方法使获得的总效益值最大.

首先说明，贪心法无法得出该问题的优化解，只能得到近似解

我们首先要决定贪心策略：

1. 选目前效益最大的物品
2. 选重量最小的物品
3. 选单位重量效益最大的物品

贪心策略的决定后就可以进行编码。

//唯一要做的就是对贪心策略有关的数组进行排序
//例如，使用贪心策略1，那就对效益值降序排序即可...
sort(target_array, target_array+length,cmp);
for(int i=0;i<length;i++)
{
    if(背包容量<该物品重量)
    {
        put;
        容量-物品重量;
        效益值+物品效益值;
    }
}
return X;

由于贪心解和精确解之间存在误差，所以我们要有能够计算和减小误差的方法。

计算：

贪心解与优化解之间误差= (优化值 - 贪心值) / 优化值 x 100%

for example:

n=2,c=y, w=[1,y], p=[10, 9y]

使用 上述贪心策略3(价值密度)

当y>1时，所有的贪心解为(1,0)，贪心值为10

而当y>10/9时，优化值为9y

所以当 1=<y<10/9时，误差==0

y>=10/9时，误差=(9y-10)/9y x 100%

 

减小误差方法：K-优化算法

概念：*对贪心算法进行改进，让误差在1/(k+1)100%之内

具体方式：

1.先将一些物品装入背包，然后对剩余物品使用贪心策略。

2.预先装入的物品不能超过K个

3.对所有物品数不超过K的物品子集进行上述过程，从中找到有最大效益值的解为K-优化算法的解。

也就是说，如果用 2-优化算法，那么 预先装入0个、1个、2个的情况都要尝试。

K优化算法需要测试的子集数目为O(n^k^)

每个子集做贪心需要时间为O(n)

K>0时，总时间开销为O(n^k+1^)

Huffman code

/*Realize by using min_heap*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

/*Huffman tree's node*/
struct Treenode{
    char code;
    Treenode *left;
    Treenode *right;
    Treenode(char x): code(x),left(NULL),right(NULL){}
};
/*heap node*/
struct heapnode{
    char c; //input's character
    int frequence;
    Treenode *node; //choose two min heapnode then let them be a tree
    heapnode(char _c,int _n):c(_c),frequence(_n){}
};

/*ini the min_heap*/
void insert2heap(vector <heapnode> & heap, heapnode hc)
{
    heap.push_back(hc);
    int len=heap.size();
    int childindex=len-1;
    int parentindex=(childindex-1)/2;// complete binary tree ~~~
    while(parentindex>=0){
        if(heap[parentindex].frequence>heap[childindex].frequence){
            heapnode temp=heap[parentindex];
            heap[parentindex]=heap[childindex];
            heap[childindex]=temp;
            
            childindex=parentindex;
            parentindex=(childindex-1)/2;// if parent > child, change them;
        }
        else{
            break;
        }
        
    }

}

/*get elem from minheap*/
heapnode remove4heap(vector<heapnode> & heap)
{
    if(heap.empty()){
        return heapnode('0',-1);
    }
    heapnode ans=heap[0];
    heap[0]=heap.back();
    heap.pop_back();//let the big one on the top,then sort this heap like ini process.

    int len=heap.size();
    int parentindex=0;
    int childindex=1;
    while(childindex<=len-1)
    {
        if((childindex!=len-1)&&(heap[childindex].frequence>heap[childindex+1].frequence)){
            childindex++;
        }

        if(heap[childindex].frequence<heap[parentindex].frequence){
            heapnode temp=heap[parentindex];
            heap[parentindex]=heap[childindex];
            heap[childindex]=temp;

            parentindex=childindex;
            childindex=2*childindex+1;
        }
        else{
            break;
        }

    }
    return ans;
}
/*ini the huffman tree! yohooooo!*/
Treenode* huffman_encode(vector<heapnode> &heap)
{
    while(!heap.empty()){
        if(heap.size()==1)
        return heap[0].node;
        else{
        heapnode x=remove4heap(heap);
        heapnode y= remove4heap(heap);

        Treenode* left;
        if(x.c!=0)// we let the newly built bintree(from two min node).c=0;and what we input !=0;
        {
            left=new Treenode(x.c);
        }
        else
        {
            left=x.node;//if has a bintree ,just use it.
        }

        Treenode* right;
        if(y.c!=0)
        {
            right=new Treenode(y.c);
        }
        else
        {
            right=y.node;
        }
        
        Treenode* z=new Treenode(0);
        z->left=left;
        z->right=right;
        heapnode hc(0,x.frequence+y.frequence);// build a new bintree...
        hc.node=z;
        insert2heap(heap,hc);
    }
    }
    return heap[0].node;
}

/*for check*/
void outputheap(vector<heapnode> &heap)
{
    for(int i=0;i<heap.size();i++){
        cout<<heap[i].c<<" : "<<heap[i].frequence<<endl;
    }
}

void outputHuffmantree(Treenode* root,string prefix)
{
    if(root->left==NULL&&root->right==NULL){
        cout<<root->code<<" "<<prefix.c_str()<<endl;
    }
    else
    {
        outputHuffmantree(root->left,prefix+"0");
        outputHuffmantree(root->right,prefix+"1");
    }
}
//use these two to output huffmancode
void outputHuffmantree(Treenode* root)
{
   if (root != NULL)
	{
		outputHuffmantree(root->left, "0");

		outputHuffmantree(root->right, "1");
	}
}

int main()
{
    vector<heapnode> heap;
    vector< pair<char,int> > ci={
        {'A',3},
        {'B',1},
        {'C',2},
        {'D',5},
        {'E',10},
    };
    for(auto x :ci){
        heapnode hc(x.first,x.second);
        insert2heap(heap,hc);
    }
    outputheap(heap);
    cout<<"------HUFFMAN CODE--------"<<endl;
    Treenode* root=huffman_encode(heap);
    outputHuffmantree(root);
    return 0;

}

拓扑排序

定义：

任务的先后顺序可用有向图表示，称为AOV网络。有向图的顶点代表任务，有向边(i,j)表示先后关系：任务i完成后才能开始任务j。

拓扑排序要求对任务进行排序，使得排序序列先后关系和AOV网定义的先后关系一致。

根据任务的有向图建立拓扑序列的过程称为拓扑排序。

---

朴素思想就是对这n个任务进行全排列，时间复杂度为O(n!)

 

而贪心法从空集开始，每步产生拓扑序列中的一个顶点W。

Greedy Startget：从当前不在拓扑序列的顶点中选取一顶点w，其所有先行节点v都在已产生的拓扑序列中，并将其加入到拓扑序列。

使用检测入度的方法确定w：入度为0的顶点要加入到拓扑序列中。

/*easy code using martix to storage graphy*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void tuopu(vector<vector<int>>& martix,vector<int> &indegree,int num_node)
{
    queue<int> ans;
    int counter=0;
    for(int i=0;i<num_node;i++)/*ini the queue*/
    {
        if(indegree[i]==0)
        { 
            ans.push(i);
            indegree[i]=-1;
        }
    }
    while(!ans.empty()){
        int temp=ans.front();
        cout<<temp<<" ";
        ans.pop();
        for(int i=0;i<num_node;i++)/*pop,then modify indegree array, then push new node!*/
        {
            if(martix[i][temp]>0)
            {
                martix[i][temp]--;
                indegree[i]--;
            }
            if(indegree[i]==0)
            {
                ans.push(i);
                indegree[i]=-1;
            }
        }
        counter++;
    }
    cout<<endl;
    if(counter!=num_node)/*check circle*/
    {
        cout<<"Circle inside!"<<endl;
    }
}

int main()
{
    int num_edge,num_node;
    cout<<"Input number of nodes and edges"<<endl;
    cin>>num_node>>num_edge;

    vector<vector<int>> martix(num_node,vector<int>(num_node) );
   
    cout<<"Input nodes of each edge:x->y"<<endl;
    int x,y;
    for(int i=0;i<num_edge;i++)
    {
        cin>>x>>y;
        martix[y][x]++;
    }
    vector<int> indegree(num_node);
    for(int i=0;i<num_node;i++)/*calcilate indegree array*/
    {
        for(int j=0;j<num_node;j++)
        {
            if(martix[i][j]!=0)
            indegree[i]++;
        }
    }
    tuopu(martix,indegree,num_node);
    return 0;
}

单源最短路经

问题描述：给定有向图G，其每条边都有一个非负的权值a[ i ] [ j ]，路径长度定义为路径上边的权值之和。给定源节点S，找出从S到图中所有其他节点的最短路径及其长度。

---

迪杰斯特拉算法 适用于权值非负情况

步骤：

1.维护一个集合S，该集合中源节点到其他节点的最短路已知，初始时该集合为空

2.从V-S集合中寻找节点v，使源节点到该点距离最小

3.更新V的临界点到源节点的距离值。

正确性原理： 如果权值非负，那么最短路的子路径也是最短路，其长度小于原来路径长度。so，我们从长度小的最短路找起。

/*easy code using martix to storage martix*/
#include <iostream>

const int max_node=50;
const int max_dis=9999;

using namespace std;

int* S;
int* visted;
int G [max_node][max_node];

void dijkstra(int num_node,int* S,int *visted,int G[max_node][max_node])
{

    int temp;
    for(int m=0;m<num_node;m++)
    {
        int min_dis=max_dis;
        for(int i=0;i<num_node;i++)
        {
            if(visted[i]==0 && S[i]<min_dis){
                min_dis=S[i];
                temp=i;
            }
        }
       
        visted[temp]=1;

        for(int i=0;i<num_node;i++)
        {
            if(G[temp][i]<max_dis)
            {
                if(S[i]>S[temp]+G[temp][i])
                {
                    S[i]=S[temp]+G[temp][i];
                }
            }
        }
    }
}

int main()
{
    int num_node,num_edge;
    cout<<"Input the number of nodes and edge"<<endl;
    cin>>num_node>>num_edge;

    S=new int [num_node];
    visted=new int[num_node];
    for(int i=0;i<num_node;i++)
    visted[i]=0;
    for(int i=0;i<num_node;i++){
        for(int j=0;j<num_node;j++){
            if(i==j)
            G[i][j]=0;
            else
            G[i][j]=max_dis;
        }
    }

    int x,y,weight;
    cout<<"Input the edge:X->Y and input the weight"<<endl;
    for(int i=0;i<num_edge;i++)
    {
        cin>>x>>y>>weight;
        G[x-1][y-1]=weight;
    }
    for(int i=0;i<num_node;i++)
    {
        S[i]=G[0][i];
    }
    visted[0]=1;

    dijkstra(num_node,S,visted,G);
    for(int i=0;i<num_node;i++)
    cout<<S[i]<<" ";
    cout<<endl;
    return 0;
}

最小生成树

问题描述：

具有n个顶点的联通的无向图G，图的每条边e有一非负权值c(e)，也称为成本，求有最小成本的生成树，每个生成树刚好具有n-1条边。

即选择n-1条边使他们形成G的最小生成树。

Kruskal 算法（以边为对象）

贪心策略：每次都选权值最小且与以前选择的边不构成cycle的边e。

需要按权值由大到小对边排序

/*easy code by merge set*/
#include <iostream>

#include <algorithm>

const int max_node=50;
int* father;
int* son;

using namespace std;

struct Edge{
    int x,y;/*x->y*/
    int weight;
};

bool mycmp(Edge a, Edge b)
{
    return a.weight<b.weight;
}

int find_root(int x)
{
    return x==father[x] ? x : find_root(father[x]); 
}

bool merge_set(int x,int y)
{
    int rootx=find_root(x);
    int rooty=find_root(y);
    if(rootx==rooty)
    return false;
    else if(son[rootx]>=son[rooty]){
        father[rooty]=rootx;
        son[rootx]=son[rooty]+son[rootx];
    }
    else
    {
        father[rootx]=rooty;
        son[rooty]=son[rooty]+son[rootx];
    }
    return true;
}

int main()
{
    int num_node,num_edge;
    int counter=0;
    int flag=0;
    int ans=0;
    cout<<"Input the number of nodes and edges"<<endl;
    cin>>num_node>>num_edge;
    Edge* edge=new Edge[num_edge];
    father= new int [num_node];
    son=new int [num_node];
    for(int i=0;i<num_node;i++){
        father[i]=i;
        son[i]=1;
    }
    cout<<"Input the edge:x->y and the weight"<<endl;
    for(int i=0;i<num_edge;i++){
        cin>>edge[i].x>>edge[i].y>>edge[i].weight;
    }
    sort(edge,edge+num_edge,mycmp);
    for(int i=0;i<num_edge-1;i++){
        if(merge_set(edge[i].x,edge[i].y))
        {
            counter++;
            ans+=edge[i].weight;
            cout<<edge[i].x<<"->"<<edge[i].y<<endl;
        }
        if(counter==num_node-1)
        {
            flag=1;
            break;
        }
    }
    if(flag)
    {
        cout<<ans<<endl;
    }
    else
    {
        cout<<"Wrong data"<<endl;
    }
    return 0;
}

Prime 算法 （以点为对象）

算法描述：

1）以某一个点开始，寻找当前该点可以访问的所有的边；
2）在已经寻找的边中发现最小边，这个边必须有一个点还没有访问过，将还没有访问的点加入我们的集合，记录添加的边；
3）寻找当前集合可以访问的所有边，重复2的过程，直到没有新的点可以加入；
4）此时由所有边构成的树即为最小生成树。

/*easy code using martix to storage graphy*/
#include <iostream>

using namespace std;

const int Max_dis=9999;

int num_node,num_edge;
int prime(int**G,int num_node,int num_edge);

int main()
{
    cout<<"Input the number of nodes and edges"<<endl;
    cin>>num_node>>num_edge;
    int **G=new int* [num_node];
    for(int i = 0;i <num_node;i++)
		G[i] = new int[num_node];
    for(int i=0;i<num_node;i++){
        for(int j=0;j<num_node;j++){
            if(i==j)
            G[i][j]=0;
            else
            G[i][j]=Max_dis;
        }
    }

    int x,y,weight;
    for(int i=0;i<num_edge;i++)
    {
        cin>>x>>y>>weight;
        G[x-1][y-1]=weight;
        G[y-1][x-1]=weight;
    }
    cout<<prime(G,num_node,num_edge)<<endl;
    return 0;
}

int prime(int**G ,int num_node,int num_edge)
{
    int start[num_node];
    int lowdis[num_node];
    int minid=0;
    int sum=0;
    for(int i=0;i<num_node;i++)
    {
        lowdis[i]=G[0][i];
    }
    start[0]=0;
    for(int i=1;i<num_node;i++)
    {
        int mindis=Max_dis;
        for(int j=1;j<num_node;j++)
        {
            if(lowdis[j]<mindis&&lowdis[j]!=0)
            {
                mindis=lowdis[j];
                minid=j;
            }
        }
        lowdis[minid]=0;
        sum+=mindis;
        for(int j=1;j<num_node;j++)
        {
            if(lowdis[j]>G[minid][j])
            {
                lowdis[j]=G[minid][j];
                start[j]=minid;
            }
        }
    }
    return sum;
}