C++(数据结构与算法)77:---贪婪算法应用之（货物装载、0/1背包问题、拓扑排序、二分覆盖、单源最短路径、最小成本生成树）

• 贪婪算法基础参阅前一篇文章：https://blog.csdn.net/qq_41453285/article/details/104439879

一、货箱装载

• 问题描述：有一艘船要状态货物，所有的货箱的大小都一样，但是货箱的重量各不相同
• 现在我们的要求是：在不超载的情况下，在货船上状态数量最多的货物

贪婪算法解决

• 思想：选择货箱时，从生下的货箱中，选择重量最小的货箱，那么就可以保证装入的货箱的数目最多
• 例如：假设n=8个货箱，x为货箱的编号，重量w分别为[100,200,50,91,150,50,20,80]，船的最大超载c=400。那么根据贪婪算法，可以在船上装载的货箱编号为7、3、6、8、4、1、5、2，总重量为390，此时得到的是最优解[x1,...x8]=[1,0,1,1,0,1,1,1]
• 定理：利用上述贪婪算法能产生最佳装载。该定理的证明如下

C++代码实现

   

    

     

      

     
     

      

       #include <iostream>
      
     
    

     

      

     
     

      

       #include <vector>
      
     
    

     

      

     
     

      

       #include <algorithm>
      
     
    

     

      

     
     

      

       using 
       namespace 
       std;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       //用于表示货箱
      
     
    

     

      

     
     

      

       struct container {
      
     
    

     

      

     
     

      

           container(
       int _id, 
       int _weight, 
       int _flag = 
       0) 
      
     
    

     

      

     
     

      

               :id(_id), weight(_weight), flag(_flag) {}
      
     
    

     

      

     
     

      
    
       int id;    
       //货箱编号
      
     
    

     

      

     
     

      
    
       int weight;
       //货箱重量
      
     
    

     

      

     
     

      
    
       int flag;  
       //用于表示是否装载进货船。0表示没有，1表示有
      
     
    

     

      

     
     

      

       };
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       /*
      
     
    

     

      

     
     

      

       参数:
      
     
    

     

      

     
     

      

        c：货箱集合
      
     
    

     

      

     
     

      

        capacity：船的最大超载容量
      
     
    

     

      

     
     

      

       */
      
     
    

     

      

     
     

      

       void containterLoading(const std::vector<container*>& c, int capacity)
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      
    
       //如果船未超载，那么进行装箱操作
      
     
    

     

      

     
     

      
    
       for (
       auto iter = c.begin(); ((iter != c.end()) && ((*iter)->weight <= capacity)); ++iter) {
      
     
    

     

      

     
     

      

               (*iter)->flag = 
       1;
      
     
    

     

      

     
     

      

               capacity -= (*iter)->weight;
      
     
    

     

      

     
     

      

           }
      
     
    

     

      

     
     

      

       }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       bool isMax(const container* p1, const container* p2)
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      
    
       return p1->weight < p2->weight;
      
     
    

     

      

     
     

      

       }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       int main()
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      
    
       //初始哈8个货箱
      
     
    

     

      

     
     

      
    
       std::
       vector<container*> vec;
      
     
    

     

      

     
     

      

           vec.push_back(
       new container(
       1, 
       100));
      
     
    

     

      

     
     

      

           vec.push_back(
       new container(
       2, 
       200));
      
     
    

     

      

     
     

      

           vec.push_back(
       new container(
       3, 
       50));
      
     
    

     

      

     
     

      

           vec.push_back(
       new container(
       4, 
       90));
      
     
    

     

      

     
     

      

           vec.push_back(
       new container(
       5, 
       150));
      
     
    

     

      

     
     

      

           vec.push_back(
       new container(
       6, 
       50));
      
     
    

     

      

     
     

      

           vec.push_back(
       new container(
       7, 
       20));
      
     
    

     

      

     
     

      

           vec.push_back(
       new container(
       8, 
       80));
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
    
       //根据container的重量对所有的货箱进行排序
      
     
    

     

      

     
     

      
    
       std::sort(vec.begin(), vec.end(), isMax);
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
    
       //装箱操作
      
     
    

     

      

     
     

      

           containterLoading(vec, 
       400);
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
    
       //打印信息
      
     
    

     

      

     
     

      
    
       std::
       cout << 
       "The number of the case being loaded is :";
      
     
    

     

      

     
     

      
    
       for (
       auto iter = vec.cbegin(); iter != vec.cend(); ++iter) {
      
     
    

     

      

     
     

      
        
       if ((*iter)->flag)
      
     
    

     

      

     
     

      
            
       std::
       cout << (*iter)->id << 
       " ";
      
     
    

     

      

     
     

      

           }
      
     
    

     

      

     
     

      
    
       std::
       cout << 
       std::
       endl;
      
     
    

     

      

     
     

      
    
       return 
       0;
      
     
    

     

      

     
     

      

       }
      
     
   

• 运行结果如下：

二、背包问题

问题描述

• 有n个物品和一个容量为c的背包。物品i的重量为Wi，价值为p。现在要从n个物品中选出一些物品装入书包中
• 现在的最佳要求是：在装包的物品总重量不超过背包的容量下，使装入的物品总价值最高
• 问题描述是：

• 约束条件是：

• Xi=1表示物品装入背包，Xi=0表示物品没有装入背包
• 0/1背包问题实际上是一个一般化的装载货箱问题，只是从每个货箱所获的价值不同

贪婪策略①

• 规则：从剩余的物品中选出可以装入背包的价值最大的物品
• 这种策略不能保证最优解
•  

贪婪策略②

• 规则：从剩余的物品中选出可以装入背包的重量最小的物品
• 这种策略也不能保证最优解

贪婪策略③

• 规则：从剩余的物品中选出可以装入背包的Pi/Wi值最大的物品
• 这种策略也不能保证最优解

启发式贪婪方法

• 上面讨论的三种算法都不能保证最优解，但是我们不必沮丧。0/1背包问题是一个NP-复杂问题
• 其中策略③虽然不能保证最优解，但是我们认为它是一个好的启发式算法，而且很多时候，它的解非常接近最优解。在一项实验中，对随机产生的600个背包问题，利用这种启发式贪婪算法得到的解有239个为最优解，有583个解与最优解相差10%，因此，所有600个解与最优解只差全在25%之内。而且算法能在O(nlogn)时间内完成，性能非常好

K阶优化

• K阶优化的原理是：
  • 首先将最多k件物品放入背包，不论它们的价值为多少
  • 如果这k件物品超过了背包最大容量c，则放弃这种操作
  • 如果这k件物品没有超过了背包最大容量c，继续从剩余的物品中按Pi/Wi值的递减顺序将物品逐个放入背包
• 现在假设n=4，w=[6,10,12,13]，p=[6,10,12,13]，c=11，Pi/Wi=[3,2.5,2,1.8]
• 当k=0时：将物品按其价值密度的非递增顺序放入背包。首先将物品1放入背包，然后是物品2。这是背包剩下的容量为5，不能再放入任何物品，因此解为x=[1,1,0,0]，此解的价值为16
• 当K=1，K=2时，结果如下：

• 修改后的贪婪启发式方法得到的解为K阶优化。也就是说，如果从解中取出k件物品，并放入另外k件物品，那么获得的结果不会原来的好。而且用这种方式获得值在最优值的(100/(k+1))%以内。因此，我们把这种启发式方法称为有界性能启发式
  • 当K=1时：保证最终结果在最佳值的50%以内
  • 当K=2时：则在33.33%以内
• 有界性能启发式方法的执行时间随k的增加而增加，需要尝试的自己数目为O()，每一个子集所需时间为O(n)。还有，物品按价值比率排序所需时间为O(nlogn)。因此当k>0时，总时间为O()
• 实际考察的性能要好的多，下图给出了600种随机测试的统计结果：

三、拓扑排序

待续

四、二分覆盖

待续

五、单源最短路径

待续

六、最小成本生成树

待续