贪心法

贪心法

<*> 贪心算法并不是从整体最优上加以考虑， 而是从局部最优考虑， 每次总是做出当前看起来最好的选择，在某种意义上的局部最优选择；

<*> 最优子结构性质 ：

<*>贪心选择性质：

1、  活动安排 ：

问题描述 ：设有n个活动集合E = {1 ,2,…,n} ，其中每个活动i都要求使用同一资源， 而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间Si和一个结束时间fi , 且Si < fi 。如果选择活动i ，则它在半开区间[Si , fi]内占用资源。若区间[Si，fi)与区间不相交，则称活动i和活动j是相容的， 也就是说Si >= fj || Sj >= fi 为真时 ，活动i和活动j是相容的。

要求：要在所给的活动集中选出最大的相容子集合；

code>> #include         #include           #include             using namespace std; class Activity { public : int id; int s;//活动开始时间 int f;//活动结束时间 public: Activity() { cin >>this->s >> this->f; } friend void Arrange(); bool operator<(Activity &A1) { if (this->f < A1.f) { return true; } else { return false; } } }; //活动集E:所给活动的集合 vector               E;//竟然要加class vector                 A;//相容标记集合 void Arrange() { sort(E.begin() + 1, E.end());//将活动按非减序列排列 int j = 0; for (int i = 1; i < E.size(); i++) { if (E[i].s >= E[j].f) { A[i] = true; j = i; } } for (int i = 0; i < A.size(); i++) { if (A[i]) { cout << E[i].id<<" "; } } } int main() { int n;//活动数量 cin >> n; E.push_back(Activity()); E[0].s = 0; E[0].f = 0; for (int i = 1; i <= n; i++) { E.push_back(Activity()); E[i].id = E[i].s; } for (int i = 0; i <= n; i++) { A.push_back(false); } Arrange(); return 0; }                              

 
2、 背包问题：
给定n种物品和一个背包。物品i的重量是wi ,其价值为vi,背包的容量为c , 问应该如何选择把哪一个物品装入背包中，使得装入背包中的物品的总价值最大？
0-1背包问题：不能部分装入物品，
背包问题：可选择装入部分物品

   
 

 

 
code>> #include           #include             #include               #include                 using namespace std; class WP { public : float w; float p; public : WP(float w, float p) { this->w = w; this->p = p; } bool operator<(WP wp) { if (1.0*w/p < 1.0*wp.w/wp.p) { return true; } else { return false; } } }; class Knapsack { public : vector                   wp; int n; float c; public : Knapsack() { cin >> this->n >> this->c; wp.push_back(WP(0 , 0)); for (int i = 1; i <= n; i++) { int in1, in2; cin>>in1>>in2; wp.push_back(WP(in1, in2)); } } }; vector < float > x; Knapsack ks; void GreedyKP() { x.push_back(0); sort(ks.wp.begin() + 1, ks.wp.end()); int sum = 0; int i; for (int i = 1; i < ks.n; i++) { x.push_back(0); } for (i = 1; i <= ks.n; i++) { if (ks.wp[i].w < ks.c) { x[i] = 1; ks.c -= ks.wp[i].w; } else { break; } } if (i < ks.n + 1) { x.push_back(1.0*ks.c/ks.wp[i].w); } for (int i = 1; i < x.size(); i++) { cout << ks.wp[i].w << " : " <                                             
 
3、  最优装载 ：
问题描述：有一批集装箱要装上载重量为c的轮船。其中集装箱i的重量为wi ， 最优装载问题要求在装载体积不受限制的情况下，将尽可能多的集装箱装上船；

     
   
 

 

code>> #include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; //最优装载问题 class Loading { public : vector 
       
         w; float c; int n; public : Loading() { cin >> this->n >> this->c; w.push_back(0); for (int i = 1; i <= this->n; i++) { float in1; cin >> in1; this->w.push_back(in1); } } }; vector 
        
          x; Loading L = Loading(); void Load() { sort(L.w.begin()+1, L.w.end()); for (int i = 0; i <= L.n; i++) { x.push_back(0); } for (int i = 1; i < L.n; i++) { if (L.w[i] <= L.c) { x[i] = 1; L.c -= L.w[i]; } else { break; } } for (int i = 1; i <= L.n; i++) { if (x[i] == 1) { cout.precision(4); cout << "weght : " << L.w[i] << endl; } } } int main() { Load(); return 0; } 
         
        
       
      
     
   
 

 
4、  哈弗曼编码 ：
问题描述：

   
 

code>> Huffman.cpp #include"BinaryTree.h" #include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; typedef BinaryTree 
       
         HuffmanTree; typedef BinaryNode 
        
          HuffmanNode; class FC { public : float m_f; char m_c; public : FC(float f = 0 , char c = ' ') { m_f = f; m_c = c; } bool operator==(float f) { if (m_f == f) { return true; } else { return false; } } }; class Huffman { public : Huffman() { cin >> n; fc.push_back(FC()); fc[0].m_f = 10000; for (int i = 1; i <= n; i++) { float in1; char in2; cin >> in1; cin >> in2; fc.push_back(FC(in1, in2)); } //生成单结点树 for (int i = 0 ; i <= n; i++) { HuffmanTree z; z.MakeTree(fc[i].m_f , HuffmanTree() , HuffmanTree()); HT.push_back(z); } } public : int n;//字符总数 vector 
         
           fc;//字符出现的频率表 vector 
          
            HT; }; Huffman huff = Huffman(); vector 
           
             code; //构建哈弗曼树 HuffmanTree MakeHuffmanTree() { //建优先级队列 priority_queue 
            
              > Q; for (int i = 0; i <= huff.n; i++) { Q.push(huff.HT[i]); } for (int i = 1; i < huff.n; i++) { HuffmanTree x, y ,z; x = Q.top(); Q.pop(); y = Q.top(); Q.pop(); float w = x.m_root->m_data + y.m_root->m_data; z.MakeTree(w , x , y); Q.push(z); } return Q.top(); } //生成编码 void Huffmancode(HuffmanNode* root) { if (root != NULL) { if (root->m_pleft == NULL && root->m_pright == NULL) { vector 
             
               ::iterator iter = find(huff.fc.begin() + 1, huff.fc.end(), root->m_data) ; cout << iter->m_c <<"的编码 : "; for (int i = 1; i < code.size(); i++) { cout << code[i]; } cout << endl; } if (root->m_pleft != NULL) { code.push_back(0); Huffmancode(root->m_pleft); } if (root->m_pright != NULL) { code.push_back(1); Huffmancode(root->m_pright); } } code.pop_back(); } //译码 void Interpret(vector 
              
                s , HuffmanNode* root) { HuffmanNode* p = root; for (int i = 0; i < s.size(); i++) { if (NULL == p->m_pleft && NULL == p->m_pright) { vector 
               
                 ::iterator iter = find(huff.fc.begin() + 1, huff.fc.end(), p->m_data); cout << iter->m_c; p = root; } if (0 == s[i]) { p = p->m_pleft; } if (1 == s[i]) { p = p->m_pright; } } cout << endl; } int main() { HuffmanTree htree; htree = MakeHuffmanTree(); code.push_back(-1); Huffmancode(htree.m_root); vector 
                
                  scode; char in; while ((in = getchar()) != '#') { scode.push_back(in-48); } //前提Huffman树已建立 Interpret(scode , htree.m_root); return 0; } //上面用到的二叉树头文件BinaryTree.h #include 
                 
                   //定义结点类型 template 
                  
                    class BinaryTree;//预引用 template 
                   
                     class BinaryNode { public: BinaryNode() :m_pleft(NULL), m_pright(NULL) {};//无参构造函数 BinaryNode(Type item, BinaryNode 
                    
                      *pleft = NULL, BinaryNode 
                     
                       *pright = NULL) :m_data(item), m_pLeft(pleft), m_pright(pright) {};//含参构造函数 //friend //friend class BinaryTree 
                      
                        ; public : BinaryNode 
                       
                         *m_pleft, *m_pright; Type m_data; }; //定义二叉树 template 
                        
                          class BinaryTree { public: BinaryTree() : m_root(NULL){ }; void MakeTree(Type item, BinaryTree 
                         
                           LBTree, BinaryTree 
                          
                            RBTree ) { m_root = new BinaryNode 
                           
                             (); m_root->m_data = item; m_root->m_pleft = LBTree.m_root; m_root->m_pright = RBTree.m_root; } friend bool operator<(BinaryTree 
                            
                              BT1 , BinaryTree 
                             
                               BT2) { if (BT1.m_root->m_data < BT2.m_root->m_data) { return false; } else { return true; } } public: BinaryNode 
                              
                                *m_root; 
                               };  
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
   
 
 5、 多机调度 ：

  




code>> #include 
    
      #include 
     
       #include 
      
        using namespace std; class JOB { public : JOB() { cin >> n >> m; jt.push_back(0); mt.push_back(0); for (int i = 1; i <= n; i++) { int in1; cin >> in1; jt.push_back(in1); } for (int i = 1; i <= m; i++) { mt.push_back(0); } }; public : int n, m; vector 
       
         jt; vector 
        
          mt; }; struct greater { bool operator()(int x , int y) const { return (x > y); } }; JOB J; void greedyJOB() { sort(J.jt.begin() + 1, J.jt.end() , greater()); int i; vector 
         
           ::iterator iter; for (i = 1; i <= J.n; i++) { if (i <= J.m) { J.mt[i] += J.jt[i]; } else { iter = min_element(J.mt.begin() + 1, J.mt.end()); *iter += J.jt[i]; } } iter = max_element(J.mt.begin() + 1, J.mt.end()); cout << *iter << endl; } int main() { greedyJOB(); return 0; } 
            
          
         
        
       
      
    
 
6、  Kruskal算法：
 
    
 
       
    
 
code>> #include"UnionSet.h" #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; class Edge { public : Edge(int i = -1, int j = -1, int weight = 1000) { this->i = i; this->j = j; this->weight = weight; } friend bool operator<(Edge E1 , Edge E2) { return (E1.weight >= E2.weight); } public: int i, j; int weight; }; class Graph { public : Graph() { cin >> vn >> en; edges.push_back(Edge()); for (int i = 1; i <= en; i++) { int in1, in2, in3; cin >> in1 >> in2 >> in3; edges.push_back(Edge(in1, in2, in3)); } } public : vector 
         
           edges;//边集 int vn;//顶点数 int en;//边数 }; Graph G; vector 
          
            minspt;//存储最小生成树中各边 //克鲁斯卡尔算法 void Kruskal() { priority_queue 
           
             > Q(G.edges.begin()+1 , G.edges.end()); /*Q.push(Edge()); for (int i = 1; i <= G.en; i++) { Q.push(G.edges[i]); } */ //初始化并查集 vector 
            
              S; S.push_back(PNode()); for (int i = 1; i <= G.vn; i++) { S.push_back(PNode(i, i)); } UnionSet U = UnionSet(S , G.vn); //边长递增序依次考察每条边 Edge s1; vector 
             
               ::iterator a ,b; for (int i = 1; i <= G.en; i++) { s1 = Q.top(); Q.pop(); a = U.Find(s1.i);//s1.i所在集合的头 b = U.Find(s1.j);//s2.j所在集合的头 if (a->data != b->data) { minspt.push_back(s1); U.Union(a->data, b->data); } } } int main() { Kruskal(); cout << "minimum_spanning_Tree : " << endl; for (int i = 0; i < minspt.size(); i++) { cout<<"( " << minspt[i].i <<" , " < 
              
                >上面用到的并查集： #pragma once #include 
               
                 #include 
                
                  #include 
                 
                   using namespace std; class PNode { public: PNode(int d = -1, int p = -1) { data = d; parent = p; }; bool operator==(int val) { return (data == val); } public: int data; int parent;//存在父子关系的就在同一个连通分支，parent是自己的结点，他就是该集合的代表； }; class UnionSet { public: UnionSet()//初始化集合 { cin >> n; s.push_back(PNode(0, 0)); for (int i = 1; i <= n; i++) { int in1; int in2; cin >> in1 >> in2; s.push_back(PNode(in1, in2)); } }; UnionSet(vector 
                  
                    s, int n) { this->s = s; this->n = n; }; void Union(int s1, int s2) { //合并成员s1， s2所在的两个连通分支 /*vector 
                   
                     ::iterator iter1, iter2; iter1 = Find(s1); iter2 = Find(s2); if(iter1->data != iter2->data) { iter2->parent = iter1->data; }*/ //合并代表s1 , s2所在的连通分支 vector 
                    
                      ::iterator iter1, iter2; iter1 = find(s.begin() + 1, s.end(), s1); iter2 = find(s.begin() + 1, s.end(), s2); iter2->parent = iter1->data; }; vector 
                     
                       ::iterator Find(int m)//查找成员m所在集合的代表，返回它的位置 { vector 
                      
                        ::iterator iter , p , q , r; iter = find(s.begin() + 1, s.end(), m); //路径压缩 p = iter; while (p->parent != p->data) { p = find(s.begin() + 1, s.end(), p->parent);//返回代表的位置 } r = iter;//指向当前 q = find(s.begin() + 1, s.end(), r->parent);//指向上级 while (q != p) { r->parent = p->parent; r = q;//上位 q = find(s.begin() + 1, s.end(), q->parent);//上位 } return p;//返回树根，即代表 } public : vector 
                       
                         s; int n; }; 
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
     
 
7、  Prim算法：
 
code>>感觉写复杂了。。。。。。 #include 
     
       #include 
      
        #include 
       
         using namespace std; class EdgeNode { public : EdgeNode(int i = 0 , int j = 0 , int w = 10000) { this->i = i; this->j = j; this->weight = w; } friend bool operator==(EdgeNode E1 , EdgeNode E2) { return ((E1.i == E2.i && E1.j == E2.j) || (E1.i == E2.j && E1.j == E2.i)); } public : int i, j; int weight; }; class Graph { public : Graph() { cin >> vn >> en; edges.push_back(EdgeNode()); for (int i = 1; i <= en; i++) { int in1, in2, in3; cin >> in1 >> in2 >> in3; edges.push_back(EdgeNode(in1, in2, in3)); } minspt.push_back(EdgeNode()); } EdgeNode Find(int i, int j) { EdgeNode e = EdgeNode(i, j, 0); vector 
        
          ::iterator iter; iter = find(edges.begin() + 1, edges.end(), e); if (iter != edges.end()) { return EdgeNode(i, j, iter->weight); } else { return EdgeNode(i, j, 10000); } } public : int vn, en; vector 
         
           edges; vector 
          
            minspt; }; Graph G; vector 
           
             closest;//closest[i] : 从V-S中的顶点i到S中最近的j顶点的相应的边 vector 
            
              s;//已选择的顶点标记为true; bool comp(EdgeNode E1 ,EdgeNode E2 )//E1 类似扫描器p, E2类似min { if (!s[E1.i]) { return (E1.weight < E2.weight); } else { return false; } } void prim() { EdgeNode e1, e2; vector 
             
               ::iterator iter; closest.push_back(EdgeNode()); //初始化closest , s; for (int i = 0; i <= G.vn; i++) { s.push_back(false); } s[0] = s[1] = true; for (int i = 1; i <= G.vn; i++)//到1的最近边 { if (!s[i]) { e1 = G.Find(i, 1); closest.push_back(EdgeNode(i, 1, e1.weight)); } else { closest.push_back(EdgeNode()); } } for (int j = 1; j < G.vn; j++) { int k = 0; iter = min_element(closest.begin() + 1, closest.end(), comp); k = iter->i; if (k) { s[k] = true;//顶点k加入S中 G.minspt.push_back(*iter); //修改closet for (int i = 1; i <= G.vn; i++) { if (!s[i]) { e1 = G.Find(i, closest[i].j); e2 = G.Find(i, k); if (e1.weight > e2.weight)//i到S中的新加的顶点k更近,更新closest { closest[i] = e2; } } } } } } int main() { prim(); cout << "minimum_spanning_Tree : " << endl; for (int i = 1; i <= G.minspt.size()-1; i++) { cout << "( " << G.minspt[i].j << " , " << G.minspt[i].i << " , " << G.minspt[i].weight << " )" << endl; } return 0; } 
              
             
            
           
          
         
        
       
     

 
 


 



 














                                                        
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/204222.html原文链接：https://javaforall.net